// Copyright (c) The Thanos Authors.
// Licensed under the Apache License 2.0.

package query

import (
	"context"
	"encoding/json"
	"fmt"
	"math"
	"os"
	"reflect"
	"sort"
	"strconv"
	"strings"
	"testing"
	"time"

	"go.uber.org/atomic"

	"github.com/efficientgo/core/testutil"
	"github.com/go-kit/log"
	"github.com/pkg/errors"
	"github.com/prometheus/common/model"
	"github.com/prometheus/prometheus/model/histogram"
	"github.com/prometheus/prometheus/model/labels"
	"github.com/prometheus/prometheus/model/timestamp"
	"github.com/prometheus/prometheus/model/value"
	"github.com/prometheus/prometheus/promql"
	"github.com/prometheus/prometheus/storage"
	"github.com/prometheus/prometheus/tsdb/chunkenc"
	"github.com/prometheus/prometheus/util/annotations"
	"github.com/prometheus/prometheus/util/gate"
	"github.com/thanos-io/thanos/pkg/logutil"

	"github.com/thanos-io/thanos/pkg/compact/downsample"
	"github.com/thanos-io/thanos/pkg/component"
	"github.com/thanos-io/thanos/pkg/dedup"
	"github.com/thanos-io/thanos/pkg/store"
	"github.com/thanos-io/thanos/pkg/store/labelpb"
	"github.com/thanos-io/thanos/pkg/store/storepb"
	storetestutil "github.com/thanos-io/thanos/pkg/store/storepb/testutil"
)

type sample struct {
	t int64
	v float64
}

func TestQueryableCreator_MaxResolution(t *testing.T) {
	t.Parallel()

	testProxy := &testStoreServer{resps: []*storepb.SeriesResponse{}}
	queryableCreator := NewQueryableCreator(nil, nil, newProxyStore(testProxy), 2, 5*time.Second, dedup.AlgorithmPenalty)

	oneHourMillis := int64(1*time.Hour) / int64(time.Millisecond)
	queryable := queryableCreator(
		false,
		nil,
		nil,
		oneHourMillis,
		false,
		false,
		nil,
		NoopSeriesStatsReporter,
	)

	q, err := queryable.Querier(0, 42)
	testutil.Ok(t, err)
	t.Cleanup(func() { testutil.Ok(t, q.Close()) })

	querierActual, ok := q.(*querier)

	testutil.Assert(t, ok == true, "expected it to be a querier")
	testutil.Assert(t, querierActual.maxResolutionMillis == oneHourMillis, "expected max source resolution to be 1 hour in milliseconds")

}

// Tests E2E how PromQL works with downsampled data.
func TestQuerier_DownsampledData(t *testing.T) {
	t.Parallel()

	testProxy := &testStoreServer{
		resps: []*storepb.SeriesResponse{
			storeSeriesResponse(t, labels.FromStrings("__name__", "a", "zzz", "a", "aaa", "bbb"), []sample{{99, 1}, {199, 5}}),                   // Downsampled chunk from Store.
			storeSeriesResponse(t, labels.FromStrings("__name__", "a", "zzz", "b", "bbbb", "eee"), []sample{{99, 3}, {199, 8}}),                  // Downsampled chunk from Store.
			storeSeriesResponse(t, labels.FromStrings("__name__", "a", "zzz", "c", "qwe", "wqeqw"), []sample{{99, 5}, {199, 15}}),                // Downsampled chunk from Store.
			storeSeriesResponse(t, labels.FromStrings("__name__", "a", "zzz", "c", "htgtreytr", "vbnbv"), []sample{{99, 123}, {199, 15}}),        // Downsampled chunk from Store.
			storeSeriesResponse(t, labels.FromStrings("__name__", "a", "zzz", "d", "asdsad", "qweqwewq"), []sample{{22, 5}, {44, 8}, {199, 15}}), // Raw chunk from Sidecar.
			storeSeriesResponse(t, labels.FromStrings("__name__", "a", "zzz", "d", "asdsad", "qweqwebb"), []sample{{22, 5}, {44, 8}, {199, 15}}), // Raw chunk from Sidecar.
		},
	}

	timeout := 10 * time.Second
	q := NewQueryableCreator(
		nil,
		nil,
		newProxyStore(testProxy),
		2,
		timeout,
		dedup.AlgorithmPenalty,
	)(false,
		nil,
		nil,
		9999999,
		false,
		false,
		nil,
		NoopSeriesStatsReporter,
	)
	engine := promql.NewEngine(
		promql.EngineOpts{
			MaxSamples: math.MaxInt32,
			Timeout:    timeout,
		},
	)

	// Minimal function to parse time.Time.
	ptm := func(in string) time.Time {
		fl, _ := strconv.ParseFloat(in, 64)
		s, ns := math.Modf(fl)
		return time.Unix(int64(s), int64(ns*float64(time.Second)))
	}

	st := ptm("0")
	ed := ptm("0.2")
	qry, err := engine.NewRangeQuery(
		context.Background(),
		q,
		promql.NewPrometheusQueryOpts(false, 0),
		"sum(a) by (zzz)",
		st,
		ed,
		100*time.Millisecond,
	)
	testutil.Ok(t, err)

	res := qry.Exec(context.Background())
	testutil.Ok(t, res.Err)
	m, err := res.Matrix()
	testutil.Ok(t, err)
	ser := []promql.Series(m)

	testutil.Assert(t, len(ser) == 4, "should return 4 series (got %d)", len(ser))

	exp := []promql.Series{
		{
			Metric: labels.FromStrings("zzz", "a"),
			Floats: []promql.FPoint{{T: 100, F: 1}, {T: 200, F: 5}},
		},
		{
			Metric: labels.FromStrings("zzz", "b"),
			Floats: []promql.FPoint{{T: 100, F: 3}, {T: 200, F: 8}},
		},
		{
			Metric: labels.FromStrings("zzz", "c"),
			// Test case: downsampling code adds all of the samples in the
			// 5 minute window of each series and pre-aggregates the data. However,
			// Prometheus engine code only takes the latest sample in each time window of
			// the retrieved data. Since we were operating in pre-aggregated data here, it lead
			// to overinflated values.
			Floats: []promql.FPoint{{T: 100, F: 128}, {T: 200, F: 30}},
		},
		{
			Metric: labels.FromStrings("zzz", "d"),
			// Test case: Prometheus engine in each time window selects the sample
			// which is closest to the boundaries and adds up the different dimensions.
			Floats: []promql.FPoint{{T: 100, F: 16}, {T: 200, F: 30}},
		},
	}

	if !reflect.DeepEqual(ser, exp) {
		t.Fatalf("response does not match, expected:\n%+v\ngot:\n%+v", exp, ser)
	}
}

var (
	realSeriesWithStaleMarkerMint             int64 = 1587690000000 // 04/24/2020 01:00:00 GMT.
	realSeriesWithStaleMarkerMaxt             int64 = 1587693600000 // 04/24/2020 02:00:00 GMT.
	expectedRealSeriesWithStaleMarkerReplica0       = []sample{
		{t: 1587690007139, v: 461993}, {t: 1587690022139, v: 462164}, {t: 1587690037139, v: 462409}, {t: 1587690052139, v: 462662}, {t: 1587690067139, v: 462824}, {t: 1587690082139, v: 462987}, {t: 1587690097155, v: 463108}, {t: 1587690112139, v: 463261}, {t: 1587690127139, v: 463465}, {t: 1587690142139, v: 463642},
		{t: 1587690157139, v: 463823}, {t: 1587690172139, v: 464065}, {t: 1587690187139, v: 464333}, {t: 1587690202139, v: 464566}, {t: 1587690217139, v: 464811}, {t: 1587690232140, v: 465032}, {t: 1587690247139, v: 465229}, {t: 1587690262139, v: 465445}, {t: 1587690277139, v: 465700}, {t: 1587690292139, v: 465884},
		{t: 1587690307139, v: 466083}, {t: 1587690322139, v: 466250}, {t: 1587690337150, v: 466534}, {t: 1587690352139, v: 466791}, {t: 1587690367139, v: 466970}, {t: 1587690382139, v: 467149}, {t: 1587690397139, v: 467265}, {t: 1587690412139, v: 467383}, {t: 1587690427139, v: 467647}, {t: 1587690442139, v: 467943},
		{t: 1587690457139, v: 468121}, {t: 1587690472139, v: 468294}, {t: 1587690487139, v: 468545}, {t: 1587690502139, v: 468676}, {t: 1587690517139, v: 468879}, {t: 1587690532139, v: 469154}, {t: 1587690547139, v: 469281}, {t: 1587690562139, v: 469512}, {t: 1587690577139, v: 469783}, {t: 1587690592139, v: 469964},
		{t: 1587690607139, v: 470171}, {t: 1587690622139, v: 470355}, {t: 1587690637139, v: 470656}, {t: 1587690652139, v: 470845}, {t: 1587690667139, v: 471077}, {t: 1587690682139, v: 471315}, {t: 1587690697139, v: 471535}, {t: 1587690712139, v: 471766}, {t: 1587690727139, v: 472002}, {t: 1587690742139, v: 472171},
		{t: 1587690757139, v: 472354}, {t: 1587690772139, v: 472736}, {t: 1587690787139, v: 472948}, {t: 1587690802139, v: 473259}, {t: 1587690817139, v: 473460}, {t: 1587690832139, v: 473753}, {t: 1587690847139, v: 474007}, {t: 1587690862139, v: 474286}, {t: 1587690877139, v: 474423}, {t: 1587690892139, v: 474788},
		{t: 1587690907139, v: 474925}, {t: 1587690922139, v: 475031}, {t: 1587690937139, v: 475316}, {t: 1587690952139, v: 475573}, {t: 1587690967139, v: 475784}, {t: 1587690982139, v: 475992}, {t: 1587690997139, v: 476341}, {t: 1587691012139, v: 476541}, {t: 1587691027139, v: 476890}, {t: 1587691042139, v: 477033},
		{t: 1587691057139, v: 477305}, {t: 1587691072139, v: 477577}, {t: 1587691087139, v: 477771}, {t: 1587691102139, v: 478012}, {t: 1587691117139, v: 478296}, {t: 1587691132139, v: 478559}, {t: 1587691147139, v: 478744}, {t: 1587691162139, v: 478950}, {t: 1587691177139, v: 479201}, {t: 1587691192139, v: 479388},
		{t: 1587691207139, v: 479638}, {t: 1587691222154, v: 479907}, {t: 1587691237139, v: 480008}, {t: 1587691252139, v: 480167}, {t: 1587691267139, v: 480472}, {t: 1587691282157, v: 480615}, {t: 1587691297139, v: 480771}, {t: 1587691312139, v: 481027}, {t: 1587691327139, v: 481212}, {t: 1587691342159, v: 481395},
		{t: 1587691357139, v: 481598}, {t: 1587691372139, v: 481786}, {t: 1587691387139, v: 482003}, {t: 1587691402141, v: 482236}, {t: 1587691417139, v: 482508}, {t: 1587691432139, v: 482636}, {t: 1587691447139, v: 482780}, {t: 1587691462139, v: 483059}, {t: 1587691477139, v: 483357}, {t: 1587691492139, v: 483566},
		{t: 1587691507139, v: 483711}, {t: 1587691522139, v: 483838}, {t: 1587691537139, v: 484091}, {t: 1587691552139, v: 484254}, {t: 1587691567139, v: 484479}, {t: 1587691582139, v: 484748}, {t: 1587691597139, v: 484978}, {t: 1587691612139, v: 485271}, {t: 1587691627139, v: 485488}, {t: 1587691642139, v: 485700},
		{t: 1587691657139, v: 485945}, {t: 1587691672139, v: 486228}, {t: 1587691687139, v: 486588}, {t: 1587691702139, v: 486691}, {t: 1587691717139, v: 486881}, {t: 1587691732139, v: 487046}, {t: 1587691747139, v: 487291}, {t: 1587691762177, v: 487410}, {t: 1587691777139, v: 487571}, {t: 1587691792139, v: 487799},
		{t: 1587691807139, v: 488050}, {t: 1587691822139, v: 488241}, {t: 1587691837139, v: 488424}, {t: 1587691852139, v: 488629}, {t: 1587691867139, v: 488875}, {t: 1587691882139, v: 489017}, {t: 1587691897139, v: 489254}, {t: 1587691912139, v: 489545}, {t: 1587691927139, v: 489778}, {t: 1587691942139, v: 489912},
		{t: 1587691957139, v: 490084}, {t: 1587691972139, v: 490364}, {t: 1587691987139, v: 490510}, {t: 1587692002139, v: 490744}, {t: 1587692017139, v: 490880}, {t: 1587692032139, v: 491025}, {t: 1587692047139, v: 491297}, {t: 1587692062155, v: 491557}, {t: 1587692077139, v: 491839}, {t: 1587692092139, v: 492065},
		{t: 1587692107139, v: 492234}, {t: 1587692122139, v: 492526}, {t: 1587692137139, v: 492767}, {t: 1587692152139, v: 492967}, {t: 1587692167139, v: 493218}, {t: 1587692182139, v: 493442}, {t: 1587692197139, v: 493647}, {t: 1587692212139, v: 493920}, {t: 1587692227139, v: 494170}, {t: 1587692242139, v: 494358},
		{t: 1587692257139, v: 494632}, {t: 1587692272139, v: 494800}, {t: 1587692287139, v: 495026}, {t: 1587692302139, v: 495222}, {t: 1587692317139, v: 495433}, {t: 1587692332139, v: 495677}, {t: 1587692347139, v: 495901}, {t: 1587692362139, v: 496107}, {t: 1587692377139, v: 496196}, {t: 1587692392139, v: 496245},
		{t: 1587692407139, v: 496300}, {t: 1587692422159, v: 496365}, {t: 1587692437139, v: 496401}, {t: 1587692452139, v: 496452}, {t: 1587692467139, v: 496532}, {t: 1587692482139, v: math.Float64frombits(value.StaleNaN)}, {t: 1587692542149, v: 5}, {t: 1587692557139, v: 101}, {t: 1587692572139, v: 312}, {t: 1587692587139, v: 508},
		{t: 1587692602144, v: 725}, {t: 1587692617139, v: 990}, {t: 1587692632139, v: 1178}, {t: 1587692647139, v: 1406}, {t: 1587692662154, v: 1640}, {t: 1587692677139, v: 1927}, {t: 1587692692139, v: 2103}, {t: 1587692707139, v: 2300}, {t: 1587692722139, v: 2482}, {t: 1587692737139, v: 2638}, {t: 1587692752139, v: 2806},
		{t: 1587692767139, v: 2979}, {t: 1587692782149, v: 3187}, {t: 1587692797139, v: 3441}, {t: 1587692812139, v: 3657}, {t: 1587692827139, v: 3827}, {t: 1587692842139, v: 3985}, {t: 1587692857139, v: 4195}, {t: 1587692872139, v: 4427}, {t: 1587692887139, v: 4646}, {t: 1587692902139, v: 4714}, {t: 1587692917153, v: 4872},
		{t: 1587692932139, v: 5131}, {t: 1587692947139, v: 5318}, {t: 1587692962139, v: 5571}, {t: 1587692977155, v: 5748}, {t: 1587692992139, v: 6030}, {t: 1587693007139, v: 6210}, {t: 1587693022139, v: 6399}, {t: 1587693037139, v: 6658}, {t: 1587693052139, v: 6896}, {t: 1587693067139, v: 7098}, {t: 1587693082139, v: 7341},
		{t: 1587693097139, v: 7495}, {t: 1587693112139, v: 7647}, {t: 1587693127139, v: 7830}, {t: 1587693142139, v: 8058}, {t: 1587693157139, v: 8209}, {t: 1587693172139, v: 8524}, {t: 1587693187139, v: 8712}, {t: 1587693202139, v: 8904}, {t: 1587693217139, v: 9103}, {t: 1587693232139, v: 9404}, {t: 1587693247155, v: 9556},
		{t: 1587693262139, v: 9777}, {t: 1587693277139, v: 9992}, {t: 1587693292139, v: 10268}, {t: 1587693307139, v: 10478}, {t: 1587693322139, v: 10754}, {t: 1587693337139, v: 10998}, {t: 1587693352139, v: 11249}, {t: 1587693367139, v: 11459}, {t: 1587693382139, v: 11778}, {t: 1587693397139, v: 12038},
		{t: 1587693412139, v: 12238}, {t: 1587693427139, v: 12450}, {t: 1587693442163, v: 12742}, {t: 1587693457139, v: 12945}, {t: 1587693472139, v: 13181}, {t: 1587693487139, v: 13440}, {t: 1587693502139, v: 13650}, {t: 1587693517139, v: 13966}, {t: 1587693532139, v: 14122}, {t: 1587693547139, v: 14327}, {t: 1587693562139, v: 14592},
		{t: 1587693577139, v: 14782}, {t: 1587693592139, v: 14956},
	}
	expectedRealSeriesWithStaleMarkerReplica1 = []sample{
		{t: 1587690005791, v: 461968}, {t: 1587690020791, v: 462151}, {t: 1587690035797, v: 462336}, {t: 1587690050791, v: 462650}, {t: 1587690065791, v: 462813}, {t: 1587690080791, v: 462987}, {t: 1587690095791, v: 463095}, {t: 1587690110791, v: 463247}, {t: 1587690125791, v: 463440}, {t: 1587690140791, v: 463642}, {t: 1587690155791, v: 463811},
		{t: 1587690170791, v: 464027}, {t: 1587690185791, v: 464308}, {t: 1587690200791, v: 464514}, {t: 1587690215791, v: 464798}, {t: 1587690230791, v: 465018}, {t: 1587690245791, v: 465215}, {t: 1587690260813, v: 465431}, {t: 1587690275791, v: 465651}, {t: 1587690290791, v: 465870}, {t: 1587690305791, v: 466070}, {t: 1587690320792, v: 466248},
		{t: 1587690335791, v: 466506}, {t: 1587690350791, v: 466766}, {t: 1587690365791, v: 466970}, {t: 1587690380791, v: 467123}, {t: 1587690395791, v: 467265}, {t: 1587690410791, v: 467383}, {t: 1587690425791, v: 467629}, {t: 1587690440791, v: 467931}, {t: 1587690455791, v: 468097}, {t: 1587690470791, v: 468281}, {t: 1587690485791, v: 468477},
		{t: 1587690500791, v: 468649}, {t: 1587690515791, v: 468867}, {t: 1587690530791, v: 469150}, {t: 1587690545791, v: 469268}, {t: 1587690560791, v: 469488}, {t: 1587690575791, v: 469742}, {t: 1587690590791, v: 469951}, {t: 1587690605791, v: 470131}, {t: 1587690620791, v: 470337}, {t: 1587690635791, v: 470631}, {t: 1587690650791, v: 470832},
		{t: 1587690665791, v: 471077}, {t: 1587690680791, v: 471311}, {t: 1587690695791, v: 471473}, {t: 1587690710791, v: 471728}, {t: 1587690725791, v: 472002}, {t: 1587690740791, v: 472158}, {t: 1587690755791, v: 472329}, {t: 1587690770791, v: 472722}, {t: 1587690785791, v: 472925}, {t: 1587690800791, v: 473220}, {t: 1587690815791, v: 473460},
		{t: 1587690830791, v: 473748}, {t: 1587690845791, v: 473968}, {t: 1587690860791, v: 474261}, {t: 1587690875791, v: 474418}, {t: 1587690890791, v: 474726}, {t: 1587690905791, v: 474913}, {t: 1587690920791, v: 475031}, {t: 1587690935791, v: 475284}, {t: 1587690950791, v: 475563}, {t: 1587690965791, v: 475762}, {t: 1587690980791, v: 475945},
		{t: 1587690995791, v: 476302}, {t: 1587691010791, v: 476501}, {t: 1587691025791, v: 476849}, {t: 1587691040800, v: 477020}, {t: 1587691055791, v: 477280}, {t: 1587691070791, v: 477549}, {t: 1587691085791, v: 477758}, {t: 1587691100817, v: 477960}, {t: 1587691115791, v: 478261}, {t: 1587691130791, v: 478559}, {t: 1587691145791, v: 478704},
		{t: 1587691160804, v: 478950}, {t: 1587691175791, v: 479173}, {t: 1587691190791, v: 479368}, {t: 1587691205791, v: 479625}, {t: 1587691220805, v: 479866}, {t: 1587691235791, v: 480008}, {t: 1587691250791, v: 480155}, {t: 1587691265791, v: 480472}, {t: 1587691280811, v: 480598}, {t: 1587691295791, v: 480771}, {t: 1587691310791, v: 480996},
		{t: 1587691325791, v: 481200}, {t: 1587691340803, v: 481381}, {t: 1587691355791, v: 481584}, {t: 1587691370791, v: 481759}, {t: 1587691385791, v: 482003}, {t: 1587691400803, v: 482189}, {t: 1587691415791, v: 482457}, {t: 1587691430791, v: 482623}, {t: 1587691445791, v: 482768}, {t: 1587691460804, v: 483036}, {t: 1587691475791, v: 483322},
		{t: 1587691490791, v: 483566}, {t: 1587691505791, v: 483709}, {t: 1587691520807, v: 483838}, {t: 1587691535791, v: 484091}, {t: 1587691550791, v: 484236}, {t: 1587691565791, v: 484454}, {t: 1587691580816, v: 484710}, {t: 1587691595791, v: 484978}, {t: 1587691610791, v: 485271}, {t: 1587691625791, v: 485476}, {t: 1587691640792, v: 485640},
		{t: 1587691655791, v: 485921}, {t: 1587691670791, v: 486201}, {t: 1587691685791, v: 486555}, {t: 1587691700791, v: 486691}, {t: 1587691715791, v: 486831}, {t: 1587691730791, v: 487033}, {t: 1587691745791, v: 487268}, {t: 1587691760803, v: 487370}, {t: 1587691775791, v: 487571}, {t: 1587691790791, v: 487787}, {t: 1587691805791, v: 488036},
		{t: 1587691820791, v: 488241}, {t: 1587691835791, v: 488411}, {t: 1587691850791, v: 488625}, {t: 1587691865791, v: 488868}, {t: 1587691880791, v: 489005}, {t: 1587691895791, v: 489237}, {t: 1587691910791, v: 489545}, {t: 1587691925791, v: 489750}, {t: 1587691940791, v: 489899}, {t: 1587691955791, v: 490048}, {t: 1587691970791, v: 490364},
		{t: 1587691985791, v: 490485}, {t: 1587692000791, v: 490722}, {t: 1587692015791, v: 490866}, {t: 1587692030791, v: 491025}, {t: 1587692045791, v: 491286}, {t: 1587692060816, v: 491543}, {t: 1587692075791, v: 491787}, {t: 1587692090791, v: 492065}, {t: 1587692105791, v: 492223}, {t: 1587692120816, v: 492501}, {t: 1587692135791, v: 492767},
		{t: 1587692150791, v: 492955}, {t: 1587692165791, v: 493194}, {t: 1587692180792, v: 493402}, {t: 1587692195791, v: 493647}, {t: 1587692210791, v: 493897}, {t: 1587692225791, v: 494117}, {t: 1587692240805, v: 494356}, {t: 1587692255791, v: 494620}, {t: 1587692270791, v: 494762}, {t: 1587692285791, v: 495001}, {t: 1587692300805, v: 495222},
		{t: 1587692315791, v: 495393}, {t: 1587692330791, v: 495662}, {t: 1587692345791, v: 495875}, {t: 1587692360801, v: 496082}, {t: 1587692375791, v: 496196}, {t: 1587692390791, v: 496245}, {t: 1587692405791, v: 496295}, {t: 1587692420791, v: 496365}, {t: 1587692435791, v: 496401}, {t: 1587692450791, v: 496452}, {t: 1587692465791, v: 496491},
		{t: 1587692480791, v: 496544}, {t: 1587692495791, v: math.Float64frombits(value.StaleNaN)}, {t: 1587692555791, v: 75}, {t: 1587692570791, v: 308}, {t: 1587692585791, v: 508}, {t: 1587692600791, v: 701}, {t: 1587692615791, v: 985}, {t: 1587692630791, v: 1153}, {t: 1587692645791, v: 1365}, {t: 1587692660791, v: 1612}, {t: 1587692675803, v: 1922}, {t: 1587692690791, v: 2103},
		{t: 1587692705791, v: 2261}, {t: 1587692720791, v: 2469}, {t: 1587692735805, v: 2625}, {t: 1587692750791, v: 2801}, {t: 1587692765791, v: 2955}, {t: 1587692780791, v: 3187}, {t: 1587692795806, v: 3428}, {t: 1587692810791, v: 3657}, {t: 1587692825791, v: 3810}, {t: 1587692840791, v: 3968}, {t: 1587692855791, v: 4195}, {t: 1587692870791, v: 4414},
		{t: 1587692885791, v: 4646}, {t: 1587692900791, v: 4689}, {t: 1587692915791, v: 4847}, {t: 1587692930791, v: 5105}, {t: 1587692945791, v: 5309}, {t: 1587692960791, v: 5521}, {t: 1587692975791, v: 5695}, {t: 1587692990810, v: 6010}, {t: 1587693005791, v: 6210}, {t: 1587693020791, v: 6394}, {t: 1587693035791, v: 6597}, {t: 1587693050791, v: 6872},
		{t: 1587693065791, v: 7098}, {t: 1587693080791, v: 7329}, {t: 1587693095791, v: 7470}, {t: 1587693110791, v: 7634}, {t: 1587693125821, v: 7830}, {t: 1587693140791, v: 8034}, {t: 1587693155791, v: 8209}, {t: 1587693170791, v: 8499}, {t: 1587693185791, v: 8688}, {t: 1587693200791, v: 8893}, {t: 1587693215791, v: 9052}, {t: 1587693230791, v: 9379},
		{t: 1587693245791, v: 9544}, {t: 1587693260791, v: 9763}, {t: 1587693275791, v: 9974}, {t: 1587693290791, v: 10242}, {t: 1587693305791, v: 10464}, {t: 1587693320803, v: 10716}, {t: 1587693335791, v: 10975}, {t: 1587693350791, v: 11232}, {t: 1587693365791, v: 11459}, {t: 1587693380791, v: 11778}, {t: 1587693395804, v: 12007}, {t: 1587693410791, v: 12206},
		{t: 1587693425791, v: 12450}, {t: 1587693440791, v: 12693}, {t: 1587693455791, v: 12908}, {t: 1587693470791, v: 13158}, {t: 1587693485791, v: 13427}, {t: 1587693500791, v: 13603}, {t: 1587693515791, v: 13927}, {t: 1587693530816, v: 14122}, {t: 1587693545791, v: 14327}, {t: 1587693560791, v: 14579}, {t: 1587693575791, v: 14759}, {t: 1587693590791, v: 14956},
	}
	expectedRealSeriesWithStaleMarkerDeduplicated = []sample{
		{t: 1587690005791, v: 461968}, {t: 1587690020791, v: 462151}, {t: 1587690035797, v: 462336}, {t: 1587690050791, v: 462650}, {t: 1587690065791, v: 462813}, {t: 1587690080791, v: 462987}, {t: 1587690095791, v: 463095}, {t: 1587690110791, v: 463247}, {t: 1587690125791, v: 463440}, {t: 1587690140791, v: 463642}, {t: 1587690155791, v: 463811},
		{t: 1587690170791, v: 464027}, {t: 1587690185791, v: 464308}, {t: 1587690200791, v: 464514}, {t: 1587690215791, v: 464798}, {t: 1587690230791, v: 465018}, {t: 1587690245791, v: 465215}, {t: 1587690260813, v: 465431}, {t: 1587690275791, v: 465651}, {t: 1587690290791, v: 465870}, {t: 1587690305791, v: 466070}, {t: 1587690320792, v: 466248},
		{t: 1587690335791, v: 466506}, {t: 1587690350791, v: 466766}, {t: 1587690365791, v: 466970}, {t: 1587690380791, v: 467123}, {t: 1587690395791, v: 467265}, {t: 1587690410791, v: 467383}, {t: 1587690425791, v: 467629}, {t: 1587690440791, v: 467931}, {t: 1587690455791, v: 468097}, {t: 1587690470791, v: 468281}, {t: 1587690485791, v: 468477},
		{t: 1587690500791, v: 468649}, {t: 1587690515791, v: 468867}, {t: 1587690530791, v: 469150}, {t: 1587690545791, v: 469268}, {t: 1587690560791, v: 469488}, {t: 1587690575791, v: 469742}, {t: 1587690590791, v: 469951}, {t: 1587690605791, v: 470131}, {t: 1587690620791, v: 470337}, {t: 1587690635791, v: 470631}, {t: 1587690650791, v: 470832},
		{t: 1587690665791, v: 471077}, {t: 1587690680791, v: 471311}, {t: 1587690695791, v: 471473}, {t: 1587690710791, v: 471728}, {t: 1587690725791, v: 472002}, {t: 1587690740791, v: 472158}, {t: 1587690755791, v: 472329}, {t: 1587690770791, v: 472722}, {t: 1587690785791, v: 472925}, {t: 1587690800791, v: 473220}, {t: 1587690815791, v: 473460},
		{t: 1587690830791, v: 473748}, {t: 1587690845791, v: 473968}, {t: 1587690860791, v: 474261}, {t: 1587690875791, v: 474418}, {t: 1587690890791, v: 474726}, {t: 1587690905791, v: 474913}, {t: 1587690920791, v: 475031}, {t: 1587690935791, v: 475284}, {t: 1587690950791, v: 475563}, {t: 1587690965791, v: 475762}, {t: 1587690980791, v: 475945},
		{t: 1587690995791, v: 476302}, {t: 1587691010791, v: 476501}, {t: 1587691025791, v: 476849}, {t: 1587691040800, v: 477020}, {t: 1587691055791, v: 477280}, {t: 1587691070791, v: 477549}, {t: 1587691085791, v: 477758}, {t: 1587691100817, v: 477960}, {t: 1587691115791, v: 478261}, {t: 1587691130791, v: 478559}, {t: 1587691145791, v: 478704},
		{t: 1587691160804, v: 478950}, {t: 1587691175791, v: 479173}, {t: 1587691190791, v: 479368}, {t: 1587691205791, v: 479625}, {t: 1587691220805, v: 479866}, {t: 1587691235791, v: 480008}, {t: 1587691250791, v: 480155}, {t: 1587691265791, v: 480472}, {t: 1587691280811, v: 480598}, {t: 1587691295791, v: 480771}, {t: 1587691310791, v: 480996},
		{t: 1587691325791, v: 481200}, {t: 1587691340803, v: 481381}, {t: 1587691355791, v: 481584}, {t: 1587691370791, v: 481759}, {t: 1587691385791, v: 482003}, {t: 1587691400803, v: 482189}, {t: 1587691415791, v: 482457}, {t: 1587691430791, v: 482623}, {t: 1587691445791, v: 482768}, {t: 1587691460804, v: 483036}, {t: 1587691475791, v: 483322},
		{t: 1587691490791, v: 483566}, {t: 1587691505791, v: 483709}, {t: 1587691520807, v: 483838}, {t: 1587691535791, v: 484091}, {t: 1587691550791, v: 484236}, {t: 1587691565791, v: 484454}, {t: 1587691580816, v: 484710}, {t: 1587691595791, v: 484978}, {t: 1587691610791, v: 485271}, {t: 1587691625791, v: 485476}, {t: 1587691640792, v: 485640},
		{t: 1587691655791, v: 485921}, {t: 1587691670791, v: 486201}, {t: 1587691685791, v: 486555}, {t: 1587691700791, v: 486691}, {t: 1587691715791, v: 486831}, {t: 1587691730791, v: 487033}, {t: 1587691745791, v: 487268}, {t: 1587691760803, v: 487370}, {t: 1587691775791, v: 487571}, {t: 1587691790791, v: 487787}, {t: 1587691805791, v: 488036},
		{t: 1587691820791, v: 488241}, {t: 1587691835791, v: 488411}, {t: 1587691850791, v: 488625}, {t: 1587691865791, v: 488868}, {t: 1587691880791, v: 489005}, {t: 1587691895791, v: 489237}, {t: 1587691910791, v: 489545}, {t: 1587691925791, v: 489750}, {t: 1587691940791, v: 489899}, {t: 1587691955791, v: 490048}, {t: 1587691970791, v: 490364},
		{t: 1587691985791, v: 490485}, {t: 1587692000791, v: 490722}, {t: 1587692015791, v: 490866}, {t: 1587692030791, v: 491025}, {t: 1587692045791, v: 491286}, {t: 1587692060816, v: 491543}, {t: 1587692075791, v: 491787}, {t: 1587692090791, v: 492065}, {t: 1587692105791, v: 492223}, {t: 1587692120816, v: 492501}, {t: 1587692135791, v: 492767},
		{t: 1587692150791, v: 492955}, {t: 1587692165791, v: 493194}, {t: 1587692180792, v: 493402}, {t: 1587692195791, v: 493647}, {t: 1587692210791, v: 493897}, {t: 1587692225791, v: 494117}, {t: 1587692240805, v: 494356}, {t: 1587692255791, v: 494620}, {t: 1587692270791, v: 494762}, {t: 1587692285791, v: 495001}, {t: 1587692300805, v: 495222},
		{t: 1587692315791, v: 495393}, {t: 1587692330791, v: 495662}, {t: 1587692345791, v: 495875}, {t: 1587692360801, v: 496082}, {t: 1587692375791, v: 496196}, {t: 1587692390791, v: 496245}, {t: 1587692405791, v: 496295}, {t: 1587692420791, v: 496365}, {t: 1587692435791, v: 496401}, {t: 1587692450791, v: 496452}, {t: 1587692465791, v: 496491},
		{t: 1587692480791, v: 496544}, {t: 1587692495791, v: math.Float64frombits(value.StaleNaN)}, {t: 1587692542149, v: 5}, {t: 1587692557139, v: 101}, {t: 1587692572139, v: 312}, {t: 1587692587139, v: 508}, {t: 1587692602144, v: 725}, {t: 1587692617139, v: 990}, {t: 1587692632139, v: 1178}, {t: 1587692647139, v: 1406}, {t: 1587692662154, v: 1640}, {t: 1587692677139, v: 1927},
		{t: 1587692692139, v: 2103}, {t: 1587692707139, v: 2300}, {t: 1587692722139, v: 2482}, {t: 1587692737139, v: 2638}, {t: 1587692752139, v: 2806}, {t: 1587692767139, v: 2979}, {t: 1587692782149, v: 3187}, {t: 1587692797139, v: 3441}, {t: 1587692812139, v: 3657}, {t: 1587692827139, v: 3827}, {t: 1587692842139, v: 3985}, {t: 1587692857139, v: 4195},
		{t: 1587692872139, v: 4427}, {t: 1587692887139, v: 4646}, {t: 1587692902139, v: 4714}, {t: 1587692917153, v: 4872}, {t: 1587692932139, v: 5131}, {t: 1587692947139, v: 5318}, {t: 1587692962139, v: 5571}, {t: 1587692977155, v: 5748}, {t: 1587692992139, v: 6030}, {t: 1587693007139, v: 6210}, {t: 1587693022139, v: 6399}, {t: 1587693037139, v: 6658},
		{t: 1587693052139, v: 6896}, {t: 1587693067139, v: 7098}, {t: 1587693082139, v: 7341}, {t: 1587693097139, v: 7495}, {t: 1587693112139, v: 7647}, {t: 1587693127139, v: 7830}, {t: 1587693142139, v: 8058}, {t: 1587693157139, v: 8209}, {t: 1587693172139, v: 8524}, {t: 1587693187139, v: 8712}, {t: 1587693202139, v: 8904}, {t: 1587693217139, v: 9103},
		{t: 1587693232139, v: 9404}, {t: 1587693247155, v: 9556}, {t: 1587693262139, v: 9777}, {t: 1587693277139, v: 9992}, {t: 1587693292139, v: 10268}, {t: 1587693307139, v: 10478}, {t: 1587693322139, v: 10754}, {t: 1587693337139, v: 10998}, {t: 1587693352139, v: 11249}, {t: 1587693367139, v: 11459}, {t: 1587693382139, v: 11778}, {t: 1587693397139, v: 12038},
		{t: 1587693412139, v: 12238}, {t: 1587693427139, v: 12450}, {t: 1587693442163, v: 12742}, {t: 1587693457139, v: 12945}, {t: 1587693472139, v: 13181}, {t: 1587693487139, v: 13440}, {t: 1587693502139, v: 13650}, {t: 1587693517139, v: 13966}, {t: 1587693532139, v: 14122}, {t: 1587693547139, v: 14327}, {t: 1587693562139, v: 14592},
		{t: 1587693577139, v: 14782}, {t: 1587693592139, v: 14956},
	}

	// For rate means that hints.func = rate.
	expectedRealSeriesWithStaleMarkerReplica0ForRate = []sample{
		{t: 1587690007139, v: 461993}, {t: 1587690022139, v: 462164}, {t: 1587690037139, v: 462409}, {t: 1587690052139, v: 462662}, {t: 1587690067139, v: 462824}, {t: 1587690082139, v: 462987}, {t: 1587690097155, v: 463108}, {t: 1587690112139, v: 463261}, {t: 1587690127139, v: 463465}, {t: 1587690142139, v: 463642}, {t: 1587690157139, v: 463823},
		{t: 1587690172139, v: 464065}, {t: 1587690187139, v: 464333}, {t: 1587690202139, v: 464566}, {t: 1587690217139, v: 464811}, {t: 1587690232140, v: 465032}, {t: 1587690247139, v: 465229}, {t: 1587690262139, v: 465445}, {t: 1587690277139, v: 465700}, {t: 1587690292139, v: 465884}, {t: 1587690307139, v: 466083}, {t: 1587690322139, v: 466250},
		{t: 1587690337150, v: 466534}, {t: 1587690352139, v: 466791}, {t: 1587690367139, v: 466970}, {t: 1587690382139, v: 467149}, {t: 1587690397139, v: 467265}, {t: 1587690412139, v: 467383}, {t: 1587690427139, v: 467647}, {t: 1587690442139, v: 467943}, {t: 1587690457139, v: 468121}, {t: 1587690472139, v: 468294}, {t: 1587690487139, v: 468545},
		{t: 1587690502139, v: 468676}, {t: 1587690517139, v: 468879}, {t: 1587690532139, v: 469154}, {t: 1587690547139, v: 469281}, {t: 1587690562139, v: 469512}, {t: 1587690577139, v: 469783}, {t: 1587690592139, v: 469964}, {t: 1587690607139, v: 470171}, {t: 1587690622139, v: 470355}, {t: 1587690637139, v: 470656}, {t: 1587690652139, v: 470845},
		{t: 1587690667139, v: 471077}, {t: 1587690682139, v: 471315}, {t: 1587690697139, v: 471535}, {t: 1587690712139, v: 471766}, {t: 1587690727139, v: 472002}, {t: 1587690742139, v: 472171}, {t: 1587690757139, v: 472354}, {t: 1587690772139, v: 472736}, {t: 1587690787139, v: 472948}, {t: 1587690802139, v: 473259}, {t: 1587690817139, v: 473460},
		{t: 1587690832139, v: 473753}, {t: 1587690847139, v: 474007}, {t: 1587690862139, v: 474286}, {t: 1587690877139, v: 474423}, {t: 1587690892139, v: 474788}, {t: 1587690907139, v: 474925}, {t: 1587690922139, v: 475031}, {t: 1587690937139, v: 475316}, {t: 1587690952139, v: 475573}, {t: 1587690967139, v: 475784}, {t: 1587690982139, v: 475992},
		{t: 1587690997139, v: 476341}, {t: 1587691012139, v: 476541}, {t: 1587691027139, v: 476890}, {t: 1587691042139, v: 477033}, {t: 1587691057139, v: 477305}, {t: 1587691072139, v: 477577}, {t: 1587691087139, v: 477771}, {t: 1587691102139, v: 478012}, {t: 1587691117139, v: 478296}, {t: 1587691132139, v: 478559}, {t: 1587691147139, v: 478744},
		{t: 1587691162139, v: 478950}, {t: 1587691177139, v: 479201}, {t: 1587691192139, v: 479388}, {t: 1587691207139, v: 479638}, {t: 1587691222154, v: 479907}, {t: 1587691237139, v: 480008}, {t: 1587691252139, v: 480167}, {t: 1587691267139, v: 480472}, {t: 1587691282157, v: 480615}, {t: 1587691297139, v: 480771}, {t: 1587691312139, v: 481027},
		{t: 1587691327139, v: 481212}, {t: 1587691342159, v: 481395}, {t: 1587691357139, v: 481598}, {t: 1587691372139, v: 481786}, {t: 1587691387139, v: 482003}, {t: 1587691402141, v: 482236}, {t: 1587691417139, v: 482508}, {t: 1587691432139, v: 482636}, {t: 1587691447139, v: 482780}, {t: 1587691462139, v: 483059}, {t: 1587691477139, v: 483357},
		{t: 1587691492139, v: 483566}, {t: 1587691507139, v: 483711}, {t: 1587691522139, v: 483838}, {t: 1587691537139, v: 484091}, {t: 1587691552139, v: 484254}, {t: 1587691567139, v: 484479}, {t: 1587691582139, v: 484748}, {t: 1587691597139, v: 484978}, {t: 1587691612139, v: 485271}, {t: 1587691627139, v: 485488}, {t: 1587691642139, v: 485700},
		{t: 1587691657139, v: 485945}, {t: 1587691672139, v: 486228}, {t: 1587691687139, v: 486588}, {t: 1587691702139, v: 486691}, {t: 1587691717139, v: 486881}, {t: 1587691732139, v: 487046}, {t: 1587691747139, v: 487291}, {t: 1587691762177, v: 487410}, {t: 1587691777139, v: 487571}, {t: 1587691792139, v: 487799}, {t: 1587691807139, v: 488050},
		{t: 1587691822139, v: 488241}, {t: 1587691837139, v: 488424}, {t: 1587691852139, v: 488629}, {t: 1587691867139, v: 488875}, {t: 1587691882139, v: 489017}, {t: 1587691897139, v: 489254}, {t: 1587691912139, v: 489545}, {t: 1587691927139, v: 489778}, {t: 1587691942139, v: 489912}, {t: 1587691957139, v: 490084}, {t: 1587691972139, v: 490364},
		{t: 1587691987139, v: 490510}, {t: 1587692002139, v: 490744}, {t: 1587692017139, v: 490880}, {t: 1587692032139, v: 491025}, {t: 1587692047139, v: 491297}, {t: 1587692062155, v: 491557}, {t: 1587692077139, v: 491839}, {t: 1587692092139, v: 492065}, {t: 1587692107139, v: 492234}, {t: 1587692122139, v: 492526}, {t: 1587692137139, v: 492767},
		{t: 1587692152139, v: 492967}, {t: 1587692167139, v: 493218}, {t: 1587692182139, v: 493442}, {t: 1587692197139, v: 493647}, {t: 1587692212139, v: 493920}, {t: 1587692227139, v: 494170}, {t: 1587692242139, v: 494358}, {t: 1587692257139, v: 494632}, {t: 1587692272139, v: 494800}, {t: 1587692287139, v: 495026}, {t: 1587692302139, v: 495222},
		{t: 1587692317139, v: 495433}, {t: 1587692332139, v: 495677}, {t: 1587692347139, v: 495901}, {t: 1587692362139, v: 496107}, {t: 1587692377139, v: 496196}, {t: 1587692392139, v: 496245}, {t: 1587692407139, v: 496300}, {t: 1587692422159, v: 496365}, {t: 1587692437139, v: 496401}, {t: 1587692452139, v: 496452}, {t: 1587692467139, v: 496532},
		{t: 1587692542149, v: 496537}, {t: 1587692557139, v: 496633}, {t: 1587692572139, v: 496844}, {t: 1587692587139, v: 497040}, {t: 1587692602144, v: 497257}, {t: 1587692617139, v: 497522}, {t: 1587692632139, v: 497710}, {t: 1587692647139, v: 497938}, {t: 1587692662154, v: 498172}, {t: 1587692677139, v: 498459}, {t: 1587692692139, v: 498635},
		{t: 1587692707139, v: 498832}, {t: 1587692722139, v: 499014}, {t: 1587692737139, v: 499170}, {t: 1587692752139, v: 499338}, {t: 1587692767139, v: 499511}, {t: 1587692782149, v: 499719}, {t: 1587692797139, v: 499973}, {t: 1587692812139, v: 500189}, {t: 1587692827139, v: 500359}, {t: 1587692842139, v: 500517}, {t: 1587692857139, v: 500727},
		{t: 1587692872139, v: 500959}, {t: 1587692887139, v: 501178}, {t: 1587692902139, v: 501246}, {t: 1587692917153, v: 501404}, {t: 1587692932139, v: 501663}, {t: 1587692947139, v: 501850}, {t: 1587692962139, v: 502103}, {t: 1587692977155, v: 502280}, {t: 1587692992139, v: 502562}, {t: 1587693007139, v: 502742}, {t: 1587693022139, v: 502931},
		{t: 1587693037139, v: 503190}, {t: 1587693052139, v: 503428}, {t: 1587693067139, v: 503630}, {t: 1587693082139, v: 503873}, {t: 1587693097139, v: 504027}, {t: 1587693112139, v: 504179}, {t: 1587693127139, v: 504362}, {t: 1587693142139, v: 504590}, {t: 1587693157139, v: 504741}, {t: 1587693172139, v: 505056}, {t: 1587693187139, v: 505244},
		{t: 1587693202139, v: 505436}, {t: 1587693217139, v: 505635}, {t: 1587693232139, v: 505936}, {t: 1587693247155, v: 506088}, {t: 1587693262139, v: 506309}, {t: 1587693277139, v: 506524}, {t: 1587693292139, v: 506800}, {t: 1587693307139, v: 507010}, {t: 1587693322139, v: 507286}, {t: 1587693337139, v: 507530}, {t: 1587693352139, v: 507781},
		{t: 1587693367139, v: 507991}, {t: 1587693382139, v: 508310}, {t: 1587693397139, v: 508570}, {t: 1587693412139, v: 508770}, {t: 1587693427139, v: 508982}, {t: 1587693442163, v: 509274}, {t: 1587693457139, v: 509477}, {t: 1587693472139, v: 509713}, {t: 1587693487139, v: 509972}, {t: 1587693502139, v: 510182}, {t: 1587693517139, v: 510498},
		{t: 1587693532139, v: 510654}, {t: 1587693547139, v: 510859}, {t: 1587693562139, v: 511124}, {t: 1587693577139, v: 511314}, {t: 1587693592139, v: 511488},
	}
	expectedRealSeriesWithStaleMarkerReplica1ForRate = []sample{
		{t: 1587690005791, v: 461968}, {t: 1587690020791, v: 462151}, {t: 1587690035797, v: 462336}, {t: 1587690050791, v: 462650}, {t: 1587690065791, v: 462813}, {t: 1587690080791, v: 462987}, {t: 1587690095791, v: 463095}, {t: 1587690110791, v: 463247}, {t: 1587690125791, v: 463440}, {t: 1587690140791, v: 463642}, {t: 1587690155791, v: 463811}, {t: 1587690170791, v: 464027},
		{t: 1587690185791, v: 464308}, {t: 1587690200791, v: 464514}, {t: 1587690215791, v: 464798}, {t: 1587690230791, v: 465018}, {t: 1587690245791, v: 465215}, {t: 1587690260813, v: 465431}, {t: 1587690275791, v: 465651}, {t: 1587690290791, v: 465870}, {t: 1587690305791, v: 466070}, {t: 1587690320792, v: 466248}, {t: 1587690335791, v: 466506}, {t: 1587690350791, v: 466766},
		{t: 1587690365791, v: 466970}, {t: 1587690380791, v: 467123}, {t: 1587690395791, v: 467265}, {t: 1587690410791, v: 467383}, {t: 1587690425791, v: 467629}, {t: 1587690440791, v: 467931}, {t: 1587690455791, v: 468097}, {t: 1587690470791, v: 468281}, {t: 1587690485791, v: 468477}, {t: 1587690500791, v: 468649}, {t: 1587690515791, v: 468867}, {t: 1587690530791, v: 469150},
		{t: 1587690545791, v: 469268}, {t: 1587690560791, v: 469488}, {t: 1587690575791, v: 469742}, {t: 1587690590791, v: 469951}, {t: 1587690605791, v: 470131}, {t: 1587690620791, v: 470337}, {t: 1587690635791, v: 470631}, {t: 1587690650791, v: 470832}, {t: 1587690665791, v: 471077}, {t: 1587690680791, v: 471311}, {t: 1587690695791, v: 471473}, {t: 1587690710791, v: 471728},
		{t: 1587690725791, v: 472002}, {t: 1587690740791, v: 472158}, {t: 1587690755791, v: 472329}, {t: 1587690770791, v: 472722}, {t: 1587690785791, v: 472925}, {t: 1587690800791, v: 473220}, {t: 1587690815791, v: 473460}, {t: 1587690830791, v: 473748}, {t: 1587690845791, v: 473968}, {t: 1587690860791, v: 474261}, {t: 1587690875791, v: 474418}, {t: 1587690890791, v: 474726},
		{t: 1587690905791, v: 474913}, {t: 1587690920791, v: 475031}, {t: 1587690935791, v: 475284}, {t: 1587690950791, v: 475563}, {t: 1587690965791, v: 475762}, {t: 1587690980791, v: 475945}, {t: 1587690995791, v: 476302}, {t: 1587691010791, v: 476501}, {t: 1587691025791, v: 476849}, {t: 1587691040800, v: 477020}, {t: 1587691055791, v: 477280}, {t: 1587691070791, v: 477549},
		{t: 1587691085791, v: 477758}, {t: 1587691100817, v: 477960}, {t: 1587691115791, v: 478261}, {t: 1587691130791, v: 478559}, {t: 1587691145791, v: 478704}, {t: 1587691160804, v: 478950}, {t: 1587691175791, v: 479173}, {t: 1587691190791, v: 479368}, {t: 1587691205791, v: 479625}, {t: 1587691220805, v: 479866}, {t: 1587691235791, v: 480008}, {t: 1587691250791, v: 480155},
		{t: 1587691265791, v: 480472}, {t: 1587691280811, v: 480598}, {t: 1587691295791, v: 480771}, {t: 1587691310791, v: 480996}, {t: 1587691325791, v: 481200}, {t: 1587691340803, v: 481381}, {t: 1587691355791, v: 481584}, {t: 1587691370791, v: 481759}, {t: 1587691385791, v: 482003}, {t: 1587691400803, v: 482189}, {t: 1587691415791, v: 482457}, {t: 1587691430791, v: 482623},
		{t: 1587691445791, v: 482768}, {t: 1587691460804, v: 483036}, {t: 1587691475791, v: 483322}, {t: 1587691490791, v: 483566}, {t: 1587691505791, v: 483709}, {t: 1587691520807, v: 483838}, {t: 1587691535791, v: 484091}, {t: 1587691550791, v: 484236}, {t: 1587691565791, v: 484454}, {t: 1587691580816, v: 484710}, {t: 1587691595791, v: 484978}, {t: 1587691610791, v: 485271},
		{t: 1587691625791, v: 485476}, {t: 1587691640792, v: 485640}, {t: 1587691655791, v: 485921}, {t: 1587691670791, v: 486201}, {t: 1587691685791, v: 486555}, {t: 1587691700791, v: 486691}, {t: 1587691715791, v: 486831}, {t: 1587691730791, v: 487033}, {t: 1587691745791, v: 487268}, {t: 1587691760803, v: 487370}, {t: 1587691775791, v: 487571}, {t: 1587691790791, v: 487787},
		{t: 1587691805791, v: 488036}, {t: 1587691820791, v: 488241}, {t: 1587691835791, v: 488411}, {t: 1587691850791, v: 488625}, {t: 1587691865791, v: 488868}, {t: 1587691880791, v: 489005}, {t: 1587691895791, v: 489237}, {t: 1587691910791, v: 489545}, {t: 1587691925791, v: 489750}, {t: 1587691940791, v: 489899}, {t: 1587691955791, v: 490048}, {t: 1587691970791, v: 490364},
		{t: 1587691985791, v: 490485}, {t: 1587692000791, v: 490722}, {t: 1587692015791, v: 490866}, {t: 1587692030791, v: 491025}, {t: 1587692045791, v: 491286}, {t: 1587692060816, v: 491543}, {t: 1587692075791, v: 491787}, {t: 1587692090791, v: 492065}, {t: 1587692105791, v: 492223}, {t: 1587692120816, v: 492501}, {t: 1587692135791, v: 492767}, {t: 1587692150791, v: 492955},
		{t: 1587692165791, v: 493194}, {t: 1587692180792, v: 493402}, {t: 1587692195791, v: 493647}, {t: 1587692210791, v: 493897}, {t: 1587692225791, v: 494117}, {t: 1587692240805, v: 494356}, {t: 1587692255791, v: 494620}, {t: 1587692270791, v: 494762}, {t: 1587692285791, v: 495001}, {t: 1587692300805, v: 495222}, {t: 1587692315791, v: 495393}, {t: 1587692330791, v: 495662},
		{t: 1587692345791, v: 495875}, {t: 1587692360801, v: 496082}, {t: 1587692375791, v: 496196}, {t: 1587692390791, v: 496245}, {t: 1587692405791, v: 496295}, {t: 1587692420791, v: 496365}, {t: 1587692435791, v: 496401}, {t: 1587692450791, v: 496452}, {t: 1587692465791, v: 496491}, {t: 1587692480791, v: 496544}, {t: 1587692555791, v: 496619}, {t: 1587692570791, v: 496852},
		{t: 1587692585791, v: 497052}, {t: 1587692600791, v: 497245}, {t: 1587692615791, v: 497529}, {t: 1587692630791, v: 497697}, {t: 1587692645791, v: 497909}, {t: 1587692660791, v: 498156}, {t: 1587692675803, v: 498466}, {t: 1587692690791, v: 498647}, {t: 1587692705791, v: 498805}, {t: 1587692720791, v: 499013}, {t: 1587692735805, v: 499169}, {t: 1587692750791, v: 499345},
		{t: 1587692765791, v: 499499}, {t: 1587692780791, v: 499731}, {t: 1587692795806, v: 499972}, {t: 1587692810791, v: 500201}, {t: 1587692825791, v: 500354}, {t: 1587692840791, v: 500512}, {t: 1587692855791, v: 500739}, {t: 1587692870791, v: 500958}, {t: 1587692885791, v: 501190}, {t: 1587692900791, v: 501233}, {t: 1587692915791, v: 501391}, {t: 1587692930791, v: 501649},
		{t: 1587692945791, v: 501853}, {t: 1587692960791, v: 502065}, {t: 1587692975791, v: 502239}, {t: 1587692990810, v: 502554}, {t: 1587693005791, v: 502754}, {t: 1587693020791, v: 502938}, {t: 1587693035791, v: 503141}, {t: 1587693050791, v: 503416}, {t: 1587693065791, v: 503642}, {t: 1587693080791, v: 503873}, {t: 1587693095791, v: 504014}, {t: 1587693110791, v: 504178},
		{t: 1587693125821, v: 504374}, {t: 1587693140791, v: 504578}, {t: 1587693155791, v: 504753}, {t: 1587693170791, v: 505043}, {t: 1587693185791, v: 505232}, {t: 1587693200791, v: 505437}, {t: 1587693215791, v: 505596}, {t: 1587693230791, v: 505923}, {t: 1587693245791, v: 506088}, {t: 1587693260791, v: 506307}, {t: 1587693275791, v: 506518}, {t: 1587693290791, v: 506786},
		{t: 1587693305791, v: 507008}, {t: 1587693320803, v: 507260}, {t: 1587693335791, v: 507519}, {t: 1587693350791, v: 507776}, {t: 1587693365791, v: 508003}, {t: 1587693380791, v: 508322}, {t: 1587693395804, v: 508551}, {t: 1587693410791, v: 508750}, {t: 1587693425791, v: 508994}, {t: 1587693440791, v: 509237}, {t: 1587693455791, v: 509452}, {t: 1587693470791, v: 509702},
		{t: 1587693485791, v: 509971}, {t: 1587693500791, v: 510147}, {t: 1587693515791, v: 510471}, {t: 1587693530816, v: 510666}, {t: 1587693545791, v: 510871}, {t: 1587693560791, v: 511123}, {t: 1587693575791, v: 511303}, {t: 1587693590791, v: 511500},
	}
	expectedRealSeriesWithStaleMarkerDeduplicatedForRate = []sample{
		{t: 1587690005791, v: 461968}, {t: 1587690020791, v: 462151}, {t: 1587690035797, v: 462336}, {t: 1587690050791, v: 462650}, {t: 1587690065791, v: 462813}, {t: 1587690080791, v: 462987}, {t: 1587690095791, v: 463095}, {t: 1587690110791, v: 463247}, {t: 1587690125791, v: 463440}, {t: 1587690140791, v: 463642}, {t: 1587690155791, v: 463811}, {t: 1587690170791, v: 464027},
		{t: 1587690185791, v: 464308}, {t: 1587690200791, v: 464514}, {t: 1587690215791, v: 464798}, {t: 1587690230791, v: 465018}, {t: 1587690245791, v: 465215}, {t: 1587690260813, v: 465431}, {t: 1587690275791, v: 465651}, {t: 1587690290791, v: 465870}, {t: 1587690305791, v: 466070}, {t: 1587690320792, v: 466248}, {t: 1587690335791, v: 466506}, {t: 1587690350791, v: 466766},
		{t: 1587690365791, v: 466970}, {t: 1587690380791, v: 467123}, {t: 1587690395791, v: 467265}, {t: 1587690410791, v: 467383}, {t: 1587690425791, v: 467629}, {t: 1587690440791, v: 467931}, {t: 1587690455791, v: 468097}, {t: 1587690470791, v: 468281}, {t: 1587690485791, v: 468477}, {t: 1587690500791, v: 468649}, {t: 1587690515791, v: 468867}, {t: 1587690530791, v: 469150},
		{t: 1587690545791, v: 469268}, {t: 1587690560791, v: 469488}, {t: 1587690575791, v: 469742}, {t: 1587690590791, v: 469951}, {t: 1587690605791, v: 470131}, {t: 1587690620791, v: 470337}, {t: 1587690635791, v: 470631}, {t: 1587690650791, v: 470832}, {t: 1587690665791, v: 471077}, {t: 1587690680791, v: 471311}, {t: 1587690695791, v: 471473}, {t: 1587690710791, v: 471728},
		{t: 1587690725791, v: 472002}, {t: 1587690740791, v: 472158}, {t: 1587690755791, v: 472329}, {t: 1587690770791, v: 472722}, {t: 1587690785791, v: 472925}, {t: 1587690800791, v: 473220}, {t: 1587690815791, v: 473460}, {t: 1587690830791, v: 473748}, {t: 1587690845791, v: 473968}, {t: 1587690860791, v: 474261}, {t: 1587690875791, v: 474418}, {t: 1587690890791, v: 474726},
		{t: 1587690905791, v: 474913}, {t: 1587690920791, v: 475031}, {t: 1587690935791, v: 475284}, {t: 1587690950791, v: 475563}, {t: 1587690965791, v: 475762}, {t: 1587690980791, v: 475945}, {t: 1587690995791, v: 476302}, {t: 1587691010791, v: 476501}, {t: 1587691025791, v: 476849}, {t: 1587691040800, v: 477020}, {t: 1587691055791, v: 477280}, {t: 1587691070791, v: 477549},
		{t: 1587691085791, v: 477758}, {t: 1587691100817, v: 477960}, {t: 1587691115791, v: 478261}, {t: 1587691130791, v: 478559}, {t: 1587691145791, v: 478704}, {t: 1587691160804, v: 478950}, {t: 1587691175791, v: 479173}, {t: 1587691190791, v: 479368}, {t: 1587691205791, v: 479625}, {t: 1587691220805, v: 479866}, {t: 1587691235791, v: 480008}, {t: 1587691250791, v: 480155},
		{t: 1587691265791, v: 480472}, {t: 1587691280811, v: 480598}, {t: 1587691295791, v: 480771}, {t: 1587691310791, v: 480996}, {t: 1587691325791, v: 481200}, {t: 1587691340803, v: 481381}, {t: 1587691355791, v: 481584}, {t: 1587691370791, v: 481759}, {t: 1587691385791, v: 482003}, {t: 1587691400803, v: 482189}, {t: 1587691415791, v: 482457}, {t: 1587691430791, v: 482623},
		{t: 1587691445791, v: 482768}, {t: 1587691460804, v: 483036}, {t: 1587691475791, v: 483322}, {t: 1587691490791, v: 483566}, {t: 1587691505791, v: 483709}, {t: 1587691520807, v: 483838}, {t: 1587691535791, v: 484091}, {t: 1587691550791, v: 484236}, {t: 1587691565791, v: 484454}, {t: 1587691580816, v: 484710}, {t: 1587691595791, v: 484978}, {t: 1587691610791, v: 485271},
		{t: 1587691625791, v: 485476}, {t: 1587691640792, v: 485640}, {t: 1587691655791, v: 485921}, {t: 1587691670791, v: 486201}, {t: 1587691685791, v: 486555}, {t: 1587691700791, v: 486691}, {t: 1587691715791, v: 486831}, {t: 1587691730791, v: 487033}, {t: 1587691745791, v: 487268}, {t: 1587691760803, v: 487370}, {t: 1587691775791, v: 487571}, {t: 1587691790791, v: 487787},
		{t: 1587691805791, v: 488036}, {t: 1587691820791, v: 488241}, {t: 1587691835791, v: 488411}, {t: 1587691850791, v: 488625}, {t: 1587691865791, v: 488868}, {t: 1587691880791, v: 489005}, {t: 1587691895791, v: 489237}, {t: 1587691910791, v: 489545}, {t: 1587691925791, v: 489750}, {t: 1587691940791, v: 489899}, {t: 1587691955791, v: 490048}, {t: 1587691970791, v: 490364},
		{t: 1587691985791, v: 490485}, {t: 1587692000791, v: 490722}, {t: 1587692015791, v: 490866}, {t: 1587692030791, v: 491025}, {t: 1587692045791, v: 491286}, {t: 1587692060816, v: 491543}, {t: 1587692075791, v: 491787}, {t: 1587692090791, v: 492065}, {t: 1587692105791, v: 492223}, {t: 1587692120816, v: 492501}, {t: 1587692135791, v: 492767}, {t: 1587692150791, v: 492955},
		{t: 1587692165791, v: 493194}, {t: 1587692180792, v: 493402}, {t: 1587692195791, v: 493647}, {t: 1587692210791, v: 493897}, {t: 1587692225791, v: 494117}, {t: 1587692240805, v: 494356}, {t: 1587692255791, v: 494620}, {t: 1587692270791, v: 494762}, {t: 1587692285791, v: 495001}, {t: 1587692300805, v: 495222}, {t: 1587692315791, v: 495393}, {t: 1587692330791, v: 495662},
		{t: 1587692345791, v: 495875}, {t: 1587692360801, v: 496082}, {t: 1587692375791, v: 496196}, {t: 1587692390791, v: 496245}, {t: 1587692405791, v: 496295}, {t: 1587692420791, v: 496365}, {t: 1587692435791, v: 496401}, {t: 1587692450791, v: 496452}, {t: 1587692465791, v: 496491}, {t: 1587692480791, v: 496544}, {t: 1587692542149, v: 496544}, {t: 1587692557139, v: 496640},
		{t: 1587692572139, v: 496851}, {t: 1587692587139, v: 497047}, {t: 1587692602144, v: 497264}, {t: 1587692617139, v: 497529}, {t: 1587692632139, v: 497717}, {t: 1587692647139, v: 497945}, {t: 1587692662154, v: 498179}, {t: 1587692677139, v: 498466}, {t: 1587692692139, v: 498642}, {t: 1587692707139, v: 498839}, {t: 1587692722139, v: 499021}, {t: 1587692737139, v: 499177},
		{t: 1587692752139, v: 499345}, {t: 1587692767139, v: 499518}, {t: 1587692782149, v: 499726}, {t: 1587692797139, v: 499980}, {t: 1587692812139, v: 500196}, {t: 1587692827139, v: 500366}, {t: 1587692842139, v: 500524}, {t: 1587692857139, v: 500734}, {t: 1587692872139, v: 500966}, {t: 1587692887139, v: 501185}, {t: 1587692902139, v: 501253}, {t: 1587692917153, v: 501411},
		{t: 1587692932139, v: 501670}, {t: 1587692947139, v: 501857}, {t: 1587692962139, v: 502110}, {t: 1587692977155, v: 502287}, {t: 1587692992139, v: 502569}, {t: 1587693007139, v: 502749}, {t: 1587693022139, v: 502938}, {t: 1587693037139, v: 503197}, {t: 1587693052139, v: 503435}, {t: 1587693067139, v: 503637}, {t: 1587693082139, v: 503880}, {t: 1587693097139, v: 504034},
		{t: 1587693112139, v: 504186}, {t: 1587693127139, v: 504369}, {t: 1587693142139, v: 504597}, {t: 1587693157139, v: 504748}, {t: 1587693172139, v: 505063}, {t: 1587693187139, v: 505251}, {t: 1587693202139, v: 505443}, {t: 1587693217139, v: 505642}, {t: 1587693232139, v: 505943}, {t: 1587693247155, v: 506095}, {t: 1587693262139, v: 506316}, {t: 1587693277139, v: 506531},
		{t: 1587693292139, v: 506807}, {t: 1587693307139, v: 507017}, {t: 1587693322139, v: 507293}, {t: 1587693337139, v: 507537}, {t: 1587693352139, v: 507788}, {t: 1587693367139, v: 507998}, {t: 1587693382139, v: 508317}, {t: 1587693397139, v: 508577}, {t: 1587693412139, v: 508777}, {t: 1587693427139, v: 508989}, {t: 1587693442163, v: 509281}, {t: 1587693457139, v: 509484},
		{t: 1587693472139, v: 509720}, {t: 1587693487139, v: 509979}, {t: 1587693502139, v: 510189}, {t: 1587693517139, v: 510505}, {t: 1587693532139, v: 510661}, {t: 1587693547139, v: 510866}, {t: 1587693562139, v: 511131}, {t: 1587693577139, v: 511321}, {t: 1587693592139, v: 511495},
	}
)

type series struct {
	lset    labels.Labels
	samples []sample
}

func (s series) Labels() labels.Labels { return s.lset }
func (s series) Iterator() chunkenc.Iterator {
	return newMockedSeriesIterator(s.samples)
}

// TestQuerier_Select_AfterPromQL tests expected results with and without deduplication after passing all data to promql.
// To test with real data:
// Collect the expected results from Prometheus or Thanos through "/api/v1/query_range" and save to a file.
// Collect raw data to be used for local storage:
//
//	scripts/insecure_grpcurl_series.sh querierGrpcIP:port '[{"name":"type","value":"current"},{"name":"_id","value":"xxx"}]' 1597823000000 1597824600000 > localStorage.json
//	Remove all white space from the file and put each series in a new line.
//	When collecting the raw data mint should be Prometheus query time minus the default look back delta(default is 5min or 300000ms)
//	For example if the Prometheus query mint is 1597823700000 the grpccurl query mint should be 1597823400000.
//
// This is because when promql displays data for a given range it looks back 5min before the requested time window.
func TestQuerier_Select_AfterPromQL(t *testing.T) {
	t.Parallel()

	logger := log.NewLogfmtLogger(os.Stderr)

	for _, tcase := range []struct {
		name               string
		storeAPI           *store.ProxyStore
		replicaLabels      []string // Replica label groups chunks by the label value and strips it from the final result.
		hints              *storage.SelectHints
		equivalentQuery    string
		lookbackDelta      time.Duration
		expected           []series
		expectedAfterDedup series
		expectedWarning    string
	}{
		{
			// Regression test 1 against https://github.com/thanos-io/thanos/issues/2890.
			name: "when switching replicas don't miss samples when set with a big enough lookback delta",
			storeAPI: newProxyStore(func() storepb.StoreServer {
				s, err := store.NewLocalStoreFromJSONMmappableFile(logger, component.Debug, labels.EmptyLabels(), "./testdata/issue2890-seriesresponses.json", store.ScanGRPCCurlProtoStreamMessages)
				testutil.Ok(t, err)
				return s
			}()),
			equivalentQuery: `cluster_version{}`,
			replicaLabels:   []string{"replica"},
			hints: &storage.SelectHints{
				Start: 1598471700000,
				End:   1598472600000,
				Step:  3000,
			},
			lookbackDelta:      15 * time.Minute,
			expected:           jsonToSeries(t, "testdata/issue2890-expected.json"),
			expectedAfterDedup: jsonToSeries(t, "testdata/issue2890-expected-dedup.json")[0],
		},
	} {

		t.Run(tcase.name, func(t *testing.T) {
			timeout := 5 * time.Minute
			e := promql.NewEngine(promql.EngineOpts{
				Logger:        logutil.GoKitLogToSlog(logger),
				Timeout:       timeout,
				MaxSamples:    math.MaxInt64,
				LookbackDelta: tcase.lookbackDelta,
			})
			for _, sc := range []struct {
				dedup    bool
				expected []series
			}{
				{dedup: false, expected: tcase.expected},
				{dedup: true, expected: []series{tcase.expectedAfterDedup}},
			} {

				resolution := time.Duration(tcase.hints.Step) * time.Millisecond
				t.Run(fmt.Sprintf("dedup=%v, resolution=%v", sc.dedup, resolution.String()), func(t *testing.T) {
					var actual []series
					// Bootstrap a local store and pass the data through promql.
					{
						g := gate.New(2)
						mq := &mockedQueryable{
							Creator: func(mint, maxt int64) storage.Querier {
								return newQuerier(nil, mint, maxt, dedup.AlgorithmPenalty, tcase.replicaLabels, nil, tcase.storeAPI, sc.dedup, 0, true, false, g, timeout, nil, NoopSeriesStatsReporter)
							},
						}
						t.Cleanup(func() {
							testutil.Ok(t, mq.Close())
						})
						q, err := e.NewRangeQuery(context.Background(), mq, promql.NewPrometheusQueryOpts(false, 0), tcase.equivalentQuery, timestamp.Time(tcase.hints.Start), timestamp.Time(tcase.hints.End), resolution)
						testutil.Ok(t, err)
						t.Cleanup(q.Close)
						res := q.Exec(context.Background())
						testutil.Ok(t, res.Err)
						actual = promqlResToSeries(res)
						if tcase.expectedWarning != "" {
							warns := res.Warnings
							testutil.Assert(t, len(warns) == 1, "expected only single warnings")
							testutil.Equals(t, tcase.expectedWarning, warns.AsErrors()[0])
						}
					}

					testutil.Equals(t, sc.expected, actual, "promql result doesn't match the expected output")
					if sc.dedup {
						testutil.Assert(t, len(actual) == 1, "expected only single response, subqueries?")
					}
				})
			}
		})
	}
}

func TestQuerier_Select(t *testing.T) {
	t.Parallel()

	logger := log.NewLogfmtLogger(os.Stderr)

	for _, tcase := range []struct {
		name           string
		storeEndpoints []storepb.StoreServer

		mint, maxt      int64
		matchers        []*labels.Matcher
		replicaLabels   []string
		hints           *storage.SelectHints
		equivalentQuery string

		expected           []series
		expectedAfterDedup []series
		expectedWarning    string
	}{
		{
			name: "select overlapping data with partial error",
			storeEndpoints: []storepb.StoreServer{
				&testStoreServer{
					resps: []*storepb.SeriesResponse{
						storeSeriesResponse(t, labels.FromStrings("a", "a"), []sample{{0, 0}, {2, 1}, {3, 2}}),
						storepb.NewWarnSeriesResponse(errors.New("partial error")),
						storeSeriesResponse(t, labels.FromStrings("a", "a"), []sample{{5, 5}, {6, 6}, {7, 7}}),
						storeSeriesResponse(t, labels.FromStrings("a", "a"), []sample{{5, 5}, {6, 66}}),
						storeSeriesResponse(t, labels.FromStrings("a", "b"), []sample{{2, 2}, {3, 3}, {4, 4}}, []sample{{1, 1}, {2, 2}, {3, 3}}),
						storeSeriesResponse(t, labels.FromStrings("a", "c"), []sample{{100, 1}, {300, 3}, {400, 4}}),
					},
				},
			},
			mint: 1, maxt: 300,
			replicaLabels:   []string{"a"},
			equivalentQuery: `{a=~"a|b|c"}`,
			matchers: []*labels.Matcher{{
				Value: "a|b|c",
				Name:  "a",
				Type:  labels.MatchRegexp,
			}},
			expected: []series{
				{
					lset:    labels.FromStrings("a", "a"),
					samples: []sample{{2, 1}, {3, 2}, {5, 5}, {6, 66}, {7, 7}},
				},
				{
					lset:    labels.FromStrings("a", "b"),
					samples: []sample{{1, 1}, {2, 2}, {3, 3}, {4, 4}},
				},
				{
					lset:    labels.FromStrings("a", "c"),
					samples: []sample{{100, 1}, {300, 3}},
				},
			},
			expectedAfterDedup: []series{{
				lset: labels.EmptyLabels(),
				// We don't expect correctness here, it's just random non-replica data.
				samples: []sample{{1, 1}, {2, 2}, {3, 3}, {5, 5}, {6, 6}, {7, 7}},
			}},
			expectedWarning: "partial error",
		},
		{
			name: "realistic data with stale marker",
			storeEndpoints: []storepb.StoreServer{func() storepb.StoreServer {
				s, err := store.NewLocalStoreFromJSONMmappableFile(logger, component.Debug, labels.EmptyLabels(), "./testdata/issue2401-seriesresponses.json", store.ScanGRPCCurlProtoStreamMessages)
				testutil.Ok(t, err)
				return s
			}()},
			mint: realSeriesWithStaleMarkerMint, maxt: realSeriesWithStaleMarkerMaxt,
			replicaLabels: []string{"replica"},
			matchers: []*labels.Matcher{{
				Value: "gitlab_transaction_cache_read_hit_count_total",
				Name:  "__name__",
				Type:  labels.MatchEqual,
			}},
			equivalentQuery: `gitlab_transaction_cache_read_hit_count_total{}`,

			expected: []series{
				{
					lset: labels.FromStrings(
						"__name__", "gitlab_transaction_cache_read_hit_count_total", "action", "widget.json", "controller", "Projects::MergeRequests::ContentController", "env", "gprd", "environment",
						"gprd", "fqdn", "web-08-sv-gprd.c.gitlab-production.internal", "instance", "web-08-sv-gprd.c.gitlab-production.internal:8083", "job", "gitlab-rails", "monitor", "app", "provider",
						"gcp", "region", "us-east", "replica", "01", "shard", "default", "stage", "main", "tier", "sv", "type", "web",
					),
					samples: expectedRealSeriesWithStaleMarkerReplica0,
				},
				{
					lset: labels.FromStrings(
						"__name__", "gitlab_transaction_cache_read_hit_count_total", "action", "widget.json", "controller", "Projects::MergeRequests::ContentController", "env", "gprd", "environment",
						"gprd", "fqdn", "web-08-sv-gprd.c.gitlab-production.internal", "instance", "web-08-sv-gprd.c.gitlab-production.internal:8083", "job", "gitlab-rails", "monitor", "app", "provider",
						"gcp", "region", "us-east", "replica", "02", "shard", "default", "stage", "main", "tier", "sv", "type", "web",
					),
					samples: expectedRealSeriesWithStaleMarkerReplica1,
				},
			},
			expectedAfterDedup: []series{{
				lset: labels.FromStrings(
					// No replica label anymore.
					"__name__", "gitlab_transaction_cache_read_hit_count_total", "action", "widget.json", "controller", "Projects::MergeRequests::ContentController", "env", "gprd", "environment",
					"gprd", "fqdn", "web-08-sv-gprd.c.gitlab-production.internal", "instance", "web-08-sv-gprd.c.gitlab-production.internal:8083", "job", "gitlab-rails", "monitor", "app", "provider",
					"gcp", "region", "us-east", "shard", "default", "stage", "main", "tier", "sv", "type", "web",
				),
				samples: expectedRealSeriesWithStaleMarkerDeduplicated,
			}},
		},
		{
			name: "realistic data with stale marker with 100000 step",
			storeEndpoints: []storepb.StoreServer{func() storepb.StoreServer {
				s, err := store.NewLocalStoreFromJSONMmappableFile(logger, component.Debug, labels.EmptyLabels(), "./testdata/issue2401-seriesresponses.json", store.ScanGRPCCurlProtoStreamMessages)
				testutil.Ok(t, err)
				return s
			}()},
			mint: realSeriesWithStaleMarkerMint, maxt: realSeriesWithStaleMarkerMaxt,
			replicaLabels: []string{"replica"},
			matchers: []*labels.Matcher{{
				Value: "gitlab_transaction_cache_read_hit_count_total",
				Name:  "__name__",
				Type:  labels.MatchEqual,
			}},
			hints: &storage.SelectHints{
				Start: realSeriesWithStaleMarkerMint,
				End:   realSeriesWithStaleMarkerMaxt,
				Step:  100000, // Should not matter.
			},
			equivalentQuery: `gitlab_transaction_cache_read_hit_count_total{}`,

			expected: []series{
				{
					lset: labels.FromStrings(
						"__name__", "gitlab_transaction_cache_read_hit_count_total", "action", "widget.json", "controller", "Projects::MergeRequests::ContentController", "env", "gprd", "environment",
						"gprd", "fqdn", "web-08-sv-gprd.c.gitlab-production.internal", "instance", "web-08-sv-gprd.c.gitlab-production.internal:8083", "job", "gitlab-rails", "monitor", "app", "provider",
						"gcp", "region", "us-east", "replica", "01", "shard", "default", "stage", "main", "tier", "sv", "type", "web",
					),
					samples: expectedRealSeriesWithStaleMarkerReplica0,
				},
				{
					lset: labels.FromStrings(
						"__name__", "gitlab_transaction_cache_read_hit_count_total", "action", "widget.json", "controller", "Projects::MergeRequests::ContentController", "env", "gprd", "environment",
						"gprd", "fqdn", "web-08-sv-gprd.c.gitlab-production.internal", "instance", "web-08-sv-gprd.c.gitlab-production.internal:8083", "job", "gitlab-rails", "monitor", "app", "provider",
						"gcp", "region", "us-east", "replica", "02", "shard", "default", "stage", "main", "tier", "sv", "type", "web",
					),
					samples: expectedRealSeriesWithStaleMarkerReplica1,
				},
			},
			expectedAfterDedup: []series{{
				lset: labels.FromStrings(
					// No replica label anymore.
					"__name__", "gitlab_transaction_cache_read_hit_count_total", "action", "widget.json", "controller", "Projects::MergeRequests::ContentController", "env", "gprd", "environment",
					"gprd", "fqdn", "web-08-sv-gprd.c.gitlab-production.internal", "instance", "web-08-sv-gprd.c.gitlab-production.internal:8083", "job", "gitlab-rails", "monitor", "app", "provider",
					"gcp", "region", "us-east", "shard", "default", "stage", "main", "tier", "sv", "type", "web",
				),
				samples: expectedRealSeriesWithStaleMarkerDeduplicated,
			}},
		},
		{
			// Regression test against https://github.com/thanos-io/thanos/issues/2401.
			// Thanks to @Superq and GitLab for real data reproducing this.
			name: "realistic data with stale marker with hints rate function",
			storeEndpoints: []storepb.StoreServer{func() storepb.StoreServer {
				s, err := store.NewLocalStoreFromJSONMmappableFile(logger, component.Debug, labels.EmptyLabels(), "./testdata/issue2401-seriesresponses.json", store.ScanGRPCCurlProtoStreamMessages)
				testutil.Ok(t, err)
				return s
			}()},
			mint: realSeriesWithStaleMarkerMint, maxt: realSeriesWithStaleMarkerMaxt,
			replicaLabels: []string{"replica"},
			matchers: []*labels.Matcher{{
				Value: "gitlab_transaction_cache_read_hit_count_total",
				Name:  "__name__",
				Type:  labels.MatchEqual,
			}},
			hints: &storage.SelectHints{
				Start: realSeriesWithStaleMarkerMint,
				End:   realSeriesWithStaleMarkerMaxt,
				// Rate triggers special case of extra downsample.CounterSeriesIterator.
				Func: "rate",
			},
			equivalentQuery: `rate(gitlab_transaction_cache_read_hit_count_total[5m])`,

			expected: []series{
				{
					lset: labels.FromStrings(
						"__name__", "gitlab_transaction_cache_read_hit_count_total", "action", "widget.json", "controller", "Projects::MergeRequests::ContentController", "env", "gprd", "environment",
						"gprd", "fqdn", "web-08-sv-gprd.c.gitlab-production.internal", "instance", "web-08-sv-gprd.c.gitlab-production.internal:8083", "job", "gitlab-rails", "monitor", "app", "provider",
						"gcp", "region", "us-east", "replica", "01", "shard", "default", "stage", "main", "tier", "sv", "type", "web",
					),
					samples: expectedRealSeriesWithStaleMarkerReplica0ForRate,
				},
				{
					lset: labels.FromStrings(
						"__name__", "gitlab_transaction_cache_read_hit_count_total", "action", "widget.json", "controller", "Projects::MergeRequests::ContentController", "env", "gprd", "environment",
						"gprd", "fqdn", "web-08-sv-gprd.c.gitlab-production.internal", "instance", "web-08-sv-gprd.c.gitlab-production.internal:8083", "job", "gitlab-rails", "monitor", "app", "provider",
						"gcp", "region", "us-east", "replica", "02", "shard", "default", "stage", "main", "tier", "sv", "type", "web",
					),
					samples: expectedRealSeriesWithStaleMarkerReplica1ForRate,
				},
			},
			expectedAfterDedup: []series{{
				lset: labels.FromStrings(
					"__name__", "gitlab_transaction_cache_read_hit_count_total", "action", "widget.json", "controller", "Projects::MergeRequests::ContentController", "env", "gprd", "environment",
					"gprd", "fqdn", "web-08-sv-gprd.c.gitlab-production.internal", "instance", "web-08-sv-gprd.c.gitlab-production.internal:8083", "job", "gitlab-rails", "monitor", "app", "provider",
					"gcp", "region", "us-east", "shard", "default", "stage", "main", "tier", "sv", "type", "web",
				),
				samples: expectedRealSeriesWithStaleMarkerDeduplicatedForRate,
			}},
		},
		// Tests with proxy (integration test with store.ProxyStore).
		{
			name: "select with proxied Store APIs that does not support without replica label",
			storeEndpoints: []storepb.StoreServer{
				&testStoreServer{
					resps: []*storepb.SeriesResponse{
						storeSeriesResponse(t, labels.FromStrings("a", "1", "r", "1", "w", "1"), []sample{{0, 0}, {2, 1}, {3, 2}}),
						storeSeriesResponse(t, labels.FromStrings("a", "1", "r", "1", "w", "1"), []sample{{5, 5}, {6, 6}, {7, 7}}),
						storeSeriesResponse(t, labels.FromStrings("a", "1", "r", "1", "x", "1"), []sample{{2, 2}, {3, 3}, {4, 4}}, []sample{{1, 1}, {2, 2}, {3, 3}}),
						storeSeriesResponse(t, labels.FromStrings("a", "1", "r", "1", "x", "1"), []sample{{100, 1}, {300, 3}, {400, 4}}),
						storeSeriesResponse(t, labels.FromStrings("a", "1", "r", "2", "w", "1"), []sample{{5, 5}, {7, 7}}),
					},
				},
				&testStoreServer{
					resps: []*storepb.SeriesResponse{
						storeSeriesResponse(t, labels.FromStrings("a", "1", "r", "2", "w", "1"), []sample{{2, 1}}),
						storeSeriesResponse(t, labels.FromStrings("a", "1", "r", "2", "w", "1"), []sample{{5, 5}, {6, 6}, {7, 7}}),
						storeSeriesResponse(t, labels.FromStrings("a", "1", "r", "2", "x", "2"), []sample{{10, 10}, {30, 30}, {40, 40}}),
					},
				},
			},
			mint: 1, maxt: 300,
			replicaLabels:   []string{"r"},
			equivalentQuery: `{a=~"1"}`,
			matchers:        []*labels.Matcher{{Name: "a", Value: "1", Type: labels.MatchRegexp}},
			expected: []series{
				{
					lset:    labels.FromStrings("a", "1", "r", "1", "w", "1"),
					samples: []sample{{2, 1}, {3, 2}, {5, 5}, {6, 6}, {7, 7}},
				},
				{
					lset:    labels.FromStrings("a", "1", "r", "1", "x", "1"),
					samples: []sample{{1, 1}, {2, 2}, {3, 3}, {4, 4}, {100, 1}, {300, 3}},
				},
				{
					lset:    labels.FromStrings("a", "1", "r", "2", "w", "1"),
					samples: []sample{{2, 1}, {5, 5}, {6, 6}, {7, 7}},
				},
				{
					lset:    labels.FromStrings("a", "1", "r", "2", "x", "2"),
					samples: []sample{{10, 10}, {30, 30}, {40, 40}},
				},
			},
			expectedAfterDedup: []series{
				{
					lset: labels.FromStrings("a", "1", "w", "1"),
					// We don't expect correctness here, it's just random non-replica data.
					samples: []sample{{2, 1}, {3, 2}, {5, 5}, {6, 6}, {7, 7}},
				},
				{
					lset: labels.FromStrings("a", "1", "x", "1"),
					// We don't expect correctness here, it's just random non-replica data.
					samples: []sample{{1, 1}, {2, 2}, {3, 3}, {100, 1}, {300, 3}},
				},
				{
					lset: labels.FromStrings("a", "1", "x", "2"),
					// We don't expect correctness here, it's just random non-replica data.
					samples: []sample{{10, 10}, {30, 30}, {40, 40}},
				},
			},
		},
		{
			name: "select with proxied Store APIs with some stores supporting without replica labels feature",
			storeEndpoints: []storepb.StoreServer{
				&testStoreServer{
					resps: []*storepb.SeriesResponse{
						storeSeriesResponse(t, labels.FromStrings("a", "1", "r", "1", "w", "1"), []sample{{0, 0}, {2, 1}, {3, 2}}),
						storeSeriesResponse(t, labels.FromStrings("a", "1", "r", "1", "w", "1"), []sample{{5, 5}, {6, 6}, {7, 7}}),
						storeSeriesResponse(t, labels.FromStrings("a", "1", "r", "1", "x", "1"), []sample{{2, 2}, {3, 3}, {4, 4}}, []sample{{1, 1}, {2, 2}, {3, 3}}),
						storeSeriesResponse(t, labels.FromStrings("a", "1", "r", "1", "x", "1"), []sample{{100, 1}, {300, 3}, {400, 4}}),
						storeSeriesResponse(t, labels.FromStrings("a", "1", "r", "2", "w", "1"), []sample{{5, 5}, {7, 7}}),
					},
					respsWithoutReplicaLabels: []*storepb.SeriesResponse{
						storeSeriesResponse(t, labels.FromStrings("a", "1", "w", "1"), []sample{{5, 5}, {7, 7}}),
						storeSeriesResponse(t, labels.FromStrings("a", "1", "w", "1"), []sample{{0, 0}, {2, 1}, {3, 2}}),
						storeSeriesResponse(t, labels.FromStrings("a", "1", "w", "1"), []sample{{5, 5}, {6, 6}, {7, 7}}),
						storeSeriesResponse(t, labels.FromStrings("a", "1", "x", "1"), []sample{{2, 2}, {3, 3}, {4, 4}}, []sample{{1, 1}, {2, 2}, {3, 3}}),
						storeSeriesResponse(t, labels.FromStrings("a", "1", "x", "1"), []sample{{100, 1}, {300, 3}, {400, 4}}),
					},
				},
				&testStoreServer{
					resps: []*storepb.SeriesResponse{
						storeSeriesResponse(t, labels.FromStrings("a", "1", "r", "2", "w", "1"), []sample{{2, 1}}),
						storeSeriesResponse(t, labels.FromStrings("a", "1", "r", "2", "w", "1"), []sample{{5, 5}, {6, 6}, {7, 7}}),
						storeSeriesResponse(t, labels.FromStrings("a", "1", "r", "2", "x", "2"), []sample{{10, 10}, {30, 30}, {40, 40}}),
					},
				},
			},
			mint: 1, maxt: 300,
			replicaLabels:   []string{"r"},
			equivalentQuery: `{a=~"1"}`,
			matchers:        []*labels.Matcher{{Name: "a", Value: "1", Type: labels.MatchRegexp}},
			expected: []series{
				{
					lset:    labels.FromStrings("a", "1", "r", "1", "w", "1"),
					samples: []sample{{2, 1}, {3, 2}, {5, 5}, {6, 6}, {7, 7}},
				},
				{
					lset:    labels.FromStrings("a", "1", "r", "1", "x", "1"),
					samples: []sample{{1, 1}, {2, 2}, {3, 3}, {4, 4}, {100, 1}, {300, 3}},
				},
				{
					lset:    labels.FromStrings("a", "1", "r", "2", "w", "1"),
					samples: []sample{{2, 1}, {5, 5}, {6, 6}, {7, 7}},
				},
				{
					lset:    labels.FromStrings("a", "1", "r", "2", "x", "2"),
					samples: []sample{{10, 10}, {30, 30}, {40, 40}},
				},
			},
			expectedAfterDedup: []series{
				{
					lset: labels.FromStrings("a", "1", "w", "1"),
					// We don't expect correctness here, it's just random non-replica data.
					samples: []sample{{2, 1}, {3, 2}, {5, 5}, {6, 6}, {7, 7}},
				},
				{
					lset: labels.FromStrings("a", "1", "x", "1"),
					// We don't expect correctness here, it's just random non-replica data.
					samples: []sample{{1, 1}, {2, 2}, {3, 3}, {100, 1}, {300, 3}},
				},
				{
					lset: labels.FromStrings("a", "1", "x", "2"),
					// We don't expect correctness here, it's just random non-replica data.
					samples: []sample{{10, 10}, {30, 30}, {40, 40}},
				},
			},
		},
	} {
		timeout := 5 * time.Second
		e := promql.NewEngine(promql.EngineOpts{
			Logger:     logutil.GoKitLogToSlog(logger),
			Timeout:    timeout,
			MaxSamples: math.MaxInt64,
		})

		t.Run(tcase.name, func(t *testing.T) {
			for _, sc := range []struct {
				dedup    bool
				expected []series
			}{
				{dedup: false, expected: tcase.expected},
				{dedup: true, expected: tcase.expectedAfterDedup},
			} {
				g := gate.New(2)
				q := newQuerier(
					nil,
					tcase.mint,
					tcase.maxt,
					dedup.AlgorithmPenalty,
					tcase.replicaLabels,
					nil,
					newProxyStore(tcase.storeEndpoints...),
					sc.dedup,
					0,
					true,
					false,
					g,
					timeout,
					nil,
					NoopSeriesStatsReporter,
				)
				t.Cleanup(func() { testutil.Ok(t, q.Close()) })

				t.Run(fmt.Sprintf("dedup=%v", sc.dedup), func(t *testing.T) {
					t.Run("querier.Select", func(t *testing.T) {
						res := q.Select(context.Background(), false, tcase.hints, tcase.matchers...)
						testSelectResponse(t, sc.expected, res)

						if tcase.expectedWarning != "" {
							warns := res.Warnings()
							testutil.Equals(t, 1, len(warns))
							testutil.Equals(t, tcase.expectedWarning, warns.AsErrors()[0].Error())
						}
					})
					// Integration test: Make sure the PromQL would select exactly the same.
					t.Run("through PromQL with 100s step", func(t *testing.T) {
						catcher := &querierResponseCatcher{t: t, Querier: q}
						q, err := e.NewRangeQuery(context.Background(), &mockedQueryable{querier: catcher}, promql.NewPrometheusQueryOpts(false, 0), tcase.equivalentQuery, timestamp.Time(tcase.mint), timestamp.Time(tcase.maxt), 100*time.Second)
						testutil.Ok(t, err)
						t.Cleanup(q.Close)

						r := q.Exec(context.Background())
						testutil.Ok(t, r.Err)

						testSelectResponse(t, sc.expected, catcher.resp[0])

						warns := catcher.warns()
						// We don't care about anything else, all should be recorded.
						testutil.Assert(t, len(catcher.resp) == 1, "expected only single response, subqueries?")

						if tcase.expectedWarning != "" {
							testutil.Equals(t, 1, len(warns))
							testutil.Equals(t, tcase.expectedWarning, warns.AsErrors()[0].Error())
						}
					})
				})
			}
		})
	}
}

func newProxyStore(storeAPIs ...storepb.StoreServer) *store.ProxyStore {
	cls := make([]store.Client, len(storeAPIs))
	for i, s := range storeAPIs {
		var withoutReplicaLabelsEnabled bool
		if srv, ok := s.(*testStoreServer); ok {
			withoutReplicaLabelsEnabled = len(srv.respsWithoutReplicaLabels) > 0
		}
		cls[i] = &storetestutil.TestClient{
			Name:        fmt.Sprintf("%v", i),
			StoreClient: storepb.ServerAsClient(s, atomic.Bool{}),
			MinTime:     math.MinInt64, MaxTime: math.MaxInt64,
			WithoutReplicaLabelsEnabled: withoutReplicaLabelsEnabled,
		}
	}

	return store.NewProxyStore(
		nil,
		nil,
		func() []store.Client { return cls },
		component.Query,
		labels.EmptyLabels(),
		0,
		store.EagerRetrieval,
	)
}

func testSelectResponse(t *testing.T, expected []series, res storage.SeriesSet) {
	var series []storage.Series
	// Use it as PromQL would do, first gather all series.
	for res.Next() {
		series = append(series, res.At())
	}
	testutil.Ok(t, res.Err())
	testutil.Equals(t, len(expected), len(series), "got %v series", func() string {
		var ret []string
		for _, s := range series {
			ret = append(ret, s.Labels().String())
		}
		return strings.Join(ret, ",")
	}())

	for i, s := range series {
		testutil.Assert(t, labels.Equal(expected[i].Labels(), s.Labels()))
		samples := expandSeries(t, s.Iterator(nil))
		expectedCpy := make([]sample, 0, len(expected[i].samples))
		for _, s := range expected[i].samples {
			v := s.v
			if value.IsStaleNaN(v) {
				// Nan != Nan, so substitute for another value.
				// This is required for testutil.Equals to work deterministically.
				v = hackyStaleMarker
			}
			expectedCpy = append(expectedCpy, sample{t: s.t, v: v})
		}
		testutil.Equals(t, expectedCpy, samples, "samples for series %v does not match", s.Labels())
	}
}

func jsonToSeries(t *testing.T, filename string) []series {
	file, err := os.ReadFile(filename)
	testutil.Ok(t, err)

	data := Response{}
	testutil.Ok(t, json.Unmarshal(file, &data), filename)

	var ss []series
	for _, ser := range data.Data.Results {
		builder := labels.NewBuilder(labels.EmptyLabels())
		for n, v := range ser.Metric {
			builder.Set(string(n), string(v))
		}

		var smpls []sample
		for _, smp := range ser.Values {
			smpls = append(smpls, sample{
				t: int64(smp.Timestamp),
				v: float64(smp.Value),
			})
		}

		ss = append(ss, series{
			lset:    builder.Labels(),
			samples: smpls,
		})
	}

	// Sort the series by their labels.
	sort.Slice(ss, func(i, j int) bool {
		return labels.Compare(ss[i].lset, ss[j].lset) <= 0
	})

	return ss
}

type Response struct {
	Status string `json:"status"`
	Data   struct {
		ResultType string       `json:"resultType"`
		Results    model.Matrix `json:"result"`
	} `json:"data"`
}

func promqlResToSeries(res *promql.Result) []series {
	matrix := res.Value.(promql.Matrix)
	series := make([]series, len(matrix))

	for i, ser := range matrix {
		series[i].lset = ser.Metric
		for _, point := range ser.Floats {
			series[i].samples = append(series[i].samples, sample{t: point.T, v: point.F})
		}
	}
	return series
}

type mockedQueryable struct {
	Creator func(int64, int64) storage.Querier
	querier storage.Querier
}

// Querier creates a querier with the provided min and max time.
// The promQL engine sets mint and it is calculated based on the default lookback delta.
func (q *mockedQueryable) Querier(mint, maxt int64) (storage.Querier, error) {
	if q.Creator == nil {
		return q.querier, nil
	}
	qq := q.Creator(mint, maxt)
	q.querier = qq
	return q.querier, nil
}

func (q *mockedQueryable) Close() error {
	defer func() {
		q.querier = nil
	}()

	if q.querier != nil {
		return q.querier.Close()
	}
	return nil
}

type querierResponseCatcher struct {
	storage.Querier
	t testing.TB

	resp []storage.SeriesSet
}

func (q *querierResponseCatcher) Select(ctx context.Context, selectSorted bool, p *storage.SelectHints, m ...*labels.Matcher) storage.SeriesSet {
	s := q.Querier.Select(ctx, selectSorted, p, m...)
	q.resp = append(q.resp, s)
	return storage.NoopSeriesSet()
}

func (q querierResponseCatcher) Close() error { return nil }

func (q *querierResponseCatcher) warns() annotations.Annotations {
	var warns annotations.Annotations
	for _, r := range q.resp {
		warns.Merge(r.Warnings())
	}
	return warns
}

type mockedSeriesIterator struct {
	cur     int
	samples []sample
}

func newMockedSeriesIterator(samples []sample) *mockedSeriesIterator {
	return &mockedSeriesIterator{samples: samples, cur: -1}
}

// TODO(rabenhorst): Native histogram support needs to be implemented, currently float type is hardcoded.
func (s *mockedSeriesIterator) Seek(t int64) chunkenc.ValueType {
	s.cur = sort.Search(len(s.samples), func(n int) bool {
		return s.samples[n].t >= t
	})

	if s.cur < len(s.samples) {
		return chunkenc.ValFloat
	}

	return chunkenc.ValNone
}

func (s *mockedSeriesIterator) At() (t int64, v float64) {
	sample := s.samples[s.cur]
	return sample.t, sample.v
}

// TODO(rabenhorst): Needs to be implemented for native histogram support.
func (s *mockedSeriesIterator) AtHistogram(*histogram.Histogram) (int64, *histogram.Histogram) {
	panic("not implemented")
}

func (s *mockedSeriesIterator) AtFloatHistogram(*histogram.FloatHistogram) (int64, *histogram.FloatHistogram) {
	panic("not implemented")
}

func (s *mockedSeriesIterator) AtT() int64 {
	return s.samples[s.cur].t
}

func (s *mockedSeriesIterator) Next() chunkenc.ValueType {
	s.cur++
	if s.cur < len(s.samples) {
		return chunkenc.ValFloat
	}

	return chunkenc.ValNone
}

func (s *mockedSeriesIterator) Err() error { return nil }

func TestQuerierWithDedupUnderstoodByPromQL_Rate(t *testing.T) {
	t.Parallel()

	logger := log.NewLogfmtLogger(os.Stderr)

	s, err := store.NewLocalStoreFromJSONMmappableFile(logger, component.Debug, labels.EmptyLabels(), "./testdata/issue2401-seriesresponses.json", store.ScanGRPCCurlProtoStreamMessages)
	testutil.Ok(t, err)

	t.Run("dedup=false", func(t *testing.T) {
		expectedLset1 := labels.FromStrings(
			"action", "widget.json", "controller", "Projects::MergeRequests::ContentController", "env", "gprd", "environment",
			"gprd", "fqdn", "web-08-sv-gprd.c.gitlab-production.internal", "instance", "web-08-sv-gprd.c.gitlab-production.internal:8083", "job", "gitlab-rails", "monitor", "app", "provider",
			"gcp", "region", "us-east", "replica", "01", "shard", "default", "stage", "main", "tier", "sv", "type", "web",
		)
		expectedLset2 := labels.FromStrings(
			"action", "widget.json", "controller", "Projects::MergeRequests::ContentController", "env", "gprd", "environment",
			"gprd", "fqdn", "web-08-sv-gprd.c.gitlab-production.internal", "instance", "web-08-sv-gprd.c.gitlab-production.internal:8083", "job", "gitlab-rails", "monitor", "app", "provider",
			"gcp", "region", "us-east", "replica", "02", "shard", "default", "stage", "main", "tier", "sv", "type", "web",
		)

		timeout := 100 * time.Second
		g := gate.New(2)
		q := newQuerier(logger, realSeriesWithStaleMarkerMint, realSeriesWithStaleMarkerMaxt, dedup.AlgorithmPenalty, []string{"replica"}, nil, newProxyStore(s), false, 0, true, false, g, timeout, nil, NoopSeriesStatsReporter)
		t.Cleanup(func() {
			testutil.Ok(t, q.Close())
		})

		e := promql.NewEngine(promql.EngineOpts{
			Logger:     logutil.GoKitLogToSlog(logger),
			Timeout:    timeout,
			MaxSamples: math.MaxInt64,
		})
		t.Run("Rate=5mStep=100s", func(t *testing.T) {
			q, err := e.NewRangeQuery(context.Background(), &mockedQueryable{querier: q}, promql.NewPrometheusQueryOpts(false, 0), `rate(gitlab_transaction_cache_read_hit_count_total[5m])`, timestamp.Time(realSeriesWithStaleMarkerMint).Add(5*time.Minute), timestamp.Time(realSeriesWithStaleMarkerMaxt), 100*time.Second)
			testutil.Ok(t, err)

			r := q.Exec(context.Background())
			testutil.Ok(t, r.Err)
			testutil.Assert(t, len(r.Warnings) == 0)

			vec, err := r.Matrix()
			testutil.Ok(t, err)
			testutil.Equals(t, promql.Matrix{
				{DropName: true, Metric: expectedLset1, Floats: []promql.FPoint{
					{T: 1587690300000, F: 13.652631578947368}, {T: 1587690400000, F: 14.049122807017543}, {T: 1587690500000, F: 13.961403508771928}, {T: 1587690600000, F: 13.617543859649121}, {T: 1587690700000, F: 14.568421052631578}, {T: 1587690800000, F: 14.989473684210525},
					{T: 1587690900000, F: 16.2}, {T: 1587691000000, F: 16.052631578947366}, {T: 1587691100000, F: 15.831578947368419}, {T: 1587691200000, F: 15.659649122807016}, {T: 1587691300000, F: 14.842105263157894}, {T: 1587691400000, F: 14.003508771929823},
					{T: 1587691500000, F: 13.782456140350876}, {T: 1587691600000, F: 13.86315789473684}, {T: 1587691700000, F: 15.270282598474376}, {T: 1587691800000, F: 14.343859649122805}, {T: 1587691900000, F: 13.975438596491227}, {T: 1587692000000, F: 13.399999999999999},
					{T: 1587692100000, F: 14.087719298245613}, {T: 1587692200000, F: 14.392982456140349}, {T: 1587692300000, F: 15.02456140350877}, {T: 1587692400000, F: 14.073684210526315}, {T: 1587692500000, F: 9.3772165751634}, {T: 1587692600000, F: 6.378947368421052},
					{T: 1587692700000, F: 8.19298245614035}, {T: 1587692800000, F: 11.91870302641626}, {T: 1587692900000, F: 13.75813610765101}, {T: 1587693000000, F: 13.087719298245613}, {T: 1587693100000, F: 13.466666666666665}, {T: 1587693200000, F: 14.028070175438595},
					{T: 1587693300000, F: 14.23859649122807}, {T: 1587693400000, F: 15.407017543859647}, {T: 1587693500000, F: 15.915789473684208}, {T: 1587693600000, F: 15.712280701754384},
				}},
				{DropName: true, Metric: expectedLset2, Floats: []promql.FPoint{
					{T: 1587690300000, F: 13.691228070175438}, {T: 1587690400000, F: 14.098245614035086}, {T: 1587690500000, F: 13.905263157894735}, {T: 1587690600000, F: 13.617543859649121}, {T: 1587690700000, F: 14.350877192982455}, {T: 1587690800000, F: 15.003508771929823},
					{T: 1587690900000, F: 16.12280701754386}, {T: 1587691000000, F: 16.049122807017543}, {T: 1587691100000, F: 15.922807017543859}, {T: 1587691200000, F: 15.63157894736842}, {T: 1587691300000, F: 14.982456140350875}, {T: 1587691400000, F: 14.187259188557553},
					{T: 1587691500000, F: 13.828070175438596}, {T: 1587691600000, F: 13.971929824561402}, {T: 1587691700000, F: 15.31994329585807}, {T: 1587691800000, F: 14.30877192982456}, {T: 1587691900000, F: 13.915789473684208}, {T: 1587692000000, F: 13.312280701754384},
					{T: 1587692100000, F: 14.136842105263156}, {T: 1587692200000, F: 14.392982456140349}, {T: 1587692300000, F: 15.014035087719297}, {T: 1587692400000, F: 14.112280701754385}, {T: 1587692500000, F: 9.421065148148148}, {T: 1587692600000, F: 6.421368067203301},
					{T: 1587692700000, F: 8.252631578947367}, {T: 1587692800000, F: 11.721237543747266}, {T: 1587692900000, F: 13.842105263157894}, {T: 1587693000000, F: 13.153509064307993}, {T: 1587693100000, F: 13.378947368421052}, {T: 1587693200000, F: 14.03157894736842},
					{T: 1587693300000, F: 14.14736842105263}, {T: 1587693400000, F: 15.343159785693986}, {T: 1587693500000, F: 15.90877192982456}, {T: 1587693600000, F: 15.761403508771927},
				}},
			}, vec)
		})
		t.Run("Rate=30mStep=500s", func(t *testing.T) {
			q, err := e.NewRangeQuery(context.Background(), &mockedQueryable{querier: q}, promql.NewPrometheusQueryOpts(false, 0), `rate(gitlab_transaction_cache_read_hit_count_total[30m])`, timestamp.Time(realSeriesWithStaleMarkerMint).Add(30*time.Minute), timestamp.Time(realSeriesWithStaleMarkerMaxt), 500*time.Second)
			testutil.Ok(t, err)

			r := q.Exec(context.Background())
			testutil.Ok(t, r.Err)
			testutil.Assert(t, len(r.Warnings) == 0)

			vec, err := r.Matrix()
			testutil.Ok(t, err)
			testutil.Equals(t, promql.Matrix{
				{DropName: true, Metric: expectedLset1, Floats: []promql.FPoint{
					{T: 1587691800000, F: 14.457142857142856}, {T: 1587692300000, F: 14.761904761904761}, {T: 1587692800000, F: 13.127170868347338}, {T: 1587693300000, F: 12.93501400560224},
				}},
				{DropName: true, Metric: expectedLset2, Floats: []promql.FPoint{
					{T: 1587691800000, F: 14.464425770308122}, {T: 1587692300000, F: 14.763025210084033}, {T: 1587692800000, F: 13.148909112808576}, {T: 1587693300000, F: 12.92829131652661},
				}},
			}, vec)
		})
	})
	// Regression test against https://github.com/thanos-io/thanos/issues/2401.
	// Rate + dedup can cause incorrectness.
	t.Run("dedup=true", func(t *testing.T) {
		expectedLset := labels.FromStrings(
			"action", "widget.json", "controller", "Projects::MergeRequests::ContentController", "env", "gprd", "environment",
			"gprd", "fqdn", "web-08-sv-gprd.c.gitlab-production.internal", "instance", "web-08-sv-gprd.c.gitlab-production.internal:8083", "job", "gitlab-rails", "monitor", "app", "provider",
			"gcp", "region", "us-east", "shard", "default", "stage", "main", "tier", "sv", "type", "web",
		)

		timeout := 5 * time.Second
		g := gate.New(2)
		q := newQuerier(logger, realSeriesWithStaleMarkerMint, realSeriesWithStaleMarkerMaxt, dedup.AlgorithmPenalty, []string{"replica"}, nil, newProxyStore(s), true, 0, true, false, g, timeout, nil, NoopSeriesStatsReporter)
		t.Cleanup(func() {
			testutil.Ok(t, q.Close())
		})

		e := promql.NewEngine(promql.EngineOpts{
			Logger:     logutil.GoKitLogToSlog(logger),
			Timeout:    timeout,
			MaxSamples: math.MaxInt64,
		})
		t.Run("Rate=5mStep=100s", func(t *testing.T) {
			q, err := e.NewRangeQuery(context.Background(), &mockedQueryable{querier: q}, promql.NewPrometheusQueryOpts(false, 0), `rate(gitlab_transaction_cache_read_hit_count_total[5m])`, timestamp.Time(realSeriesWithStaleMarkerMint).Add(5*time.Minute), timestamp.Time(realSeriesWithStaleMarkerMaxt), 100*time.Second)
			testutil.Ok(t, err)

			r := q.Exec(context.Background())
			testutil.Ok(t, r.Err)
			testutil.Assert(t, len(r.Warnings) == 0)

			vec, err := r.Matrix()
			testutil.Ok(t, err)
			testutil.Equals(t, promql.Matrix{
				{DropName: true, Metric: expectedLset, Floats: []promql.FPoint{
					{T: 1587690300000, F: 13.691228070175438}, {T: 1587690400000, F: 14.098245614035086}, {T: 1587690500000, F: 13.905263157894735}, {T: 1587690600000, F: 13.617543859649121},
					{T: 1587690700000, F: 14.350877192982455}, {T: 1587690800000, F: 15.003508771929823}, {T: 1587690900000, F: 16.12280701754386}, {T: 1587691000000, F: 16.049122807017543},
					{T: 1587691100000, F: 15.922807017543859}, {T: 1587691200000, F: 15.63157894736842}, {T: 1587691300000, F: 14.982456140350875}, {T: 1587691400000, F: 14.187259188557553},
					{T: 1587691500000, F: 13.828070175438596}, {T: 1587691600000, F: 13.971929824561402}, {T: 1587691700000, F: 15.31994329585807}, {T: 1587691800000, F: 14.30877192982456},
					{T: 1587691900000, F: 13.915789473684208}, {T: 1587692000000, F: 13.312280701754384}, {T: 1587692100000, F: 14.136842105263156}, {T: 1587692200000, F: 14.392982456140349},
					{T: 1587692300000, F: 15.014035087719297}, {T: 1587692400000, F: 14.112280701754385}, {T: 1587692500000, F: 9.421065148148148}, {T: 1587692600000, F: 6.3736754978451735},
					{T: 1587692700000, F: 8.19632056099571}, {T: 1587692800000, F: 11.91870302641626}, {T: 1587692900000, F: 13.75813610765101}, {T: 1587693000000, F: 13.087719298245613},
					{T: 1587693100000, F: 13.466666666666665}, {T: 1587693200000, F: 14.028070175438595}, {T: 1587693300000, F: 14.23859649122807}, {T: 1587693400000, F: 15.407017543859647},
					{T: 1587693500000, F: 15.915789473684208}, {T: 1587693600000, F: 15.712280701754384},
				}},
			}, vec)
		})
		t.Run("Rate=30mStep=500s", func(t *testing.T) {
			q, err := e.NewRangeQuery(context.Background(), &mockedQueryable{querier: q}, promql.NewPrometheusQueryOpts(false, 0), `rate(gitlab_transaction_cache_read_hit_count_total[30m])`, timestamp.Time(realSeriesWithStaleMarkerMint).Add(30*time.Minute), timestamp.Time(realSeriesWithStaleMarkerMaxt), 500*time.Second)
			testutil.Ok(t, err)

			r := q.Exec(context.Background())
			testutil.Ok(t, r.Err)
			testutil.Assert(t, len(r.Warnings) == 0)

			vec, err := r.Matrix()
			testutil.Ok(t, err)
			testutil.Equals(t, promql.Matrix{
				{DropName: true, Metric: expectedLset, Floats: []promql.FPoint{
					{T: 1587691800000, F: 14.464425770308122},
					{T: 1587692300000, F: 14.763025210084033},
					{T: 1587692800000, F: 13.143575607888273},
					{T: 1587693300000, F: 12.930291298224088},
				}},
			}, vec)
		})
	})
}

const hackyStaleMarker = float64(-99999999)

func expandSeries(t testing.TB, it chunkenc.Iterator) (res []sample) {
	for it.Next() != chunkenc.ValNone {
		t, v := it.At()
		// Nan != Nan, so substitute for another value.
		// This is required for testutil.Equals to work deterministically.
		if math.IsNaN(v) {
			v = hackyStaleMarker
		}
		res = append(res, sample{t, v})
	}
	testutil.Ok(t, it.Err())
	return res
}

type testStoreServer struct {
	// This field just exist to pseudo-implement the unused methods of the interface.
	storepb.StoreServer

	resps                     []*storepb.SeriesResponse
	respsWithoutReplicaLabels []*storepb.SeriesResponse
}

func (s *testStoreServer) Series(r *storepb.SeriesRequest, srv storepb.Store_SeriesServer) error {
	resps := s.resps

	if len(r.WithoutReplicaLabels) > 0 && len(s.respsWithoutReplicaLabels) > 0 {
		// If `respsWithoutReplicaLabels` is present, we simulate server that supports without replica label feature.
		resps = s.respsWithoutReplicaLabels
	}
	for _, resp := range resps {
		err := srv.Send(resp)
		if err != nil {
			return err
		}
	}
	return nil
}

// storeSeriesResponse creates test storepb.SeriesResponse that includes series with single chunk that stores all the given samples.
func storeSeriesResponse(t testing.TB, lset labels.Labels, smplChunks ...[]sample) *storepb.SeriesResponse {
	var s storepb.Series

	lset.Range(func(l labels.Label) {
		s.Labels = append(s.Labels, labelpb.ZLabel{Name: l.Name, Value: l.Value})
	})

	for _, smpls := range smplChunks {
		c := chunkenc.NewXORChunk()
		a, err := c.Appender()
		testutil.Ok(t, err)

		for _, smpl := range smpls {
			a.Append(smpl.t, smpl.v)
		}

		ch := storepb.AggrChunk{
			MinTime: smpls[0].t,
			MaxTime: smpls[len(smpls)-1].t,
			Raw:     &storepb.Chunk{Type: storepb.Chunk_XOR, Data: c.Bytes()},
		}

		s.Chunks = append(s.Chunks, ch)
	}
	return storepb.NewSeriesResponse(&s)
}

func TestMaxResolutionFromSelectHints(t *testing.T) {
	twoMinRange := int64(2 * 60 * 1000)
	for _, tc := range []struct {
		name                string
		maxResolutionMillis int64
		hints               storage.SelectHints
		expected            int64
	}{
		{
			name: "no range",
			hints: storage.SelectHints{
				Range: 0,
			},
			maxResolutionMillis: downsample.ResLevel1,
			expected:            downsample.ResLevel1,
		},
		{
			name: "no function",
			hints: storage.SelectHints{
				Range: twoMinRange,
			},
			maxResolutionMillis: downsample.ResLevel1,
			expected:            downsample.ResLevel1,
		},
		{
			name: "function doesn't impact resolution",
			hints: storage.SelectHints{
				Range: twoMinRange,
				Func:  "max_over_time",
			},
			maxResolutionMillis: downsample.ResLevel1,
			expected:            downsample.ResLevel1,
		},
		{
			name: "rate",
			hints: storage.SelectHints{
				Range: twoMinRange,
				Func:  "rate",
			},
			maxResolutionMillis: downsample.ResLevel1,
			expected:            twoMinRange / 2,
		},
		{
			name: "rate",
			hints: storage.SelectHints{
				Range: twoMinRange,
				Func:  "rate",
			},
			maxResolutionMillis: downsample.ResLevel1,
			expected:            twoMinRange / 2,
		},
		{
			name: "irate",
			hints: storage.SelectHints{
				Range: twoMinRange,
				Func:  "irate",
			},
			maxResolutionMillis: downsample.ResLevel1,
			expected:            twoMinRange / 2,
		},
		{
			name: "increase",
			hints: storage.SelectHints{
				Range: twoMinRange,
				Func:  "increase",
			},
			maxResolutionMillis: downsample.ResLevel1,
			expected:            twoMinRange / 2,
		},
		{
			name: "delta",
			hints: storage.SelectHints{
				Range: twoMinRange,
				Func:  "delta",
			},
			maxResolutionMillis: downsample.ResLevel1,
			expected:            twoMinRange / 2,
		},
		{
			name: "idelta",
			hints: storage.SelectHints{
				Range: twoMinRange,
				Func:  "idelta",
			},
			maxResolutionMillis: downsample.ResLevel1,
			expected:            twoMinRange / 2,
		},
		{
			name: "deriv",
			hints: storage.SelectHints{
				Range: twoMinRange,
				Func:  "deriv",
			},
			maxResolutionMillis: downsample.ResLevel1,
			expected:            twoMinRange / 2,
		},
		{
			name: "predict_linear",
			hints: storage.SelectHints{
				Range: twoMinRange,
				Func:  "predict_linear",
			},
			maxResolutionMillis: downsample.ResLevel1,
			expected:            twoMinRange / 2,
		},
		{
			name: "holt_winters",
			hints: storage.SelectHints{
				Range: twoMinRange,
				Func:  "holt_winters",
			},
			maxResolutionMillis: downsample.ResLevel1,
			expected:            twoMinRange / 2,
		},
		{
			name: "double_exponential_smoothing",
			hints: storage.SelectHints{
				Range: twoMinRange,
				Func:  "double_exponential_smoothing",
			},
			maxResolutionMillis: downsample.ResLevel1,
			expected:            twoMinRange / 2,
		},
	} {
		t.Run(tc.name, func(t *testing.T) {
			res := maxResolutionFromSelectHints(tc.maxResolutionMillis, tc.hints.Range, tc.hints.Func)
			testutil.Equals(t, tc.expected, res)
		})
	}
}
